壹、题目描述 ¶
贰、题解 ¶
涉及到一个叫做反序表的东西......
反序表的定义如下：
对于一个排列 \(\{a_i\}\)，定义其反序表为 \(\{d_i\}\) 满足
\[d_i=\sum_{j<i}[a_j>a_i] \]序列 \(\{d_i\}\) 有一些很奇妙的性质：
- \(d_i\in[0,i-1]\)，显然法；
- \(d_i\) 的取值只与 \(\{a_i\}\) 的顺序有关，不同的 \(d_i\) 之间相互独立；
- \(\{a_i\},\{d_i\}\) 满足一一映射，即一个 \(\{a_i\}\) 对应一个 \(\{d_i\}\)，反之亦然；
前两点比较好理解，对于最后一点，我不知道如何从数学上严谨证明，但是我可以给出一种通过 \(\{d_i\}\) 构造出 \(\{a_i\}\) 的方法，并且这个构造方法构造出的 \(\{a_i\}\) 显然是唯一的：
从 \(d_n\) 入手，显然，\(a_n=n-d_n\)，并对 \(n-d_n\) 打上已经使用的标记，接下来，依次遍历 \(n-1,n-2,...,1\)，并依次执行以下操作：
- 假设当前为 \(i\)，那么 \(a_i'=n-d_i\)；
- 如果 \(a_i'\) 没有被使用过，那么 \(a_i=a_i'\) 并打上标记，执行 \(i\leftarrow i-1\) 并回到 \(1\)，若不成立，则进入 \(3\)；
- 找到最大的 \(x<a_i'\) 并且 \(x\) 没有被打上标记，那么 \(a_i=x\) 并打上标记，执行 \(i\leftarrow i-1\) 并回到 \(1\)；
不难看出，这样构造的序列一定是唯一且对应 \(\{d_i\}\) 的。
那么这个题就很简单了，由于一个排列的轮数取决于最大的 \(d_i\)，使用简单容斥即可，式子就不写了，实在不会就看看代码吧。
叁、参考代码 ¶
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
#define NDUBUG
#include<cassert>
namespace Elaina{
#define rep(i, l, r) for(int i=(l), i##_end_=(r); i<=i##_end_; ++i)
#define drep(i, l, r) for(int i=(l), i##_end_=(r); i>=i##_end_; --i)
#define fi first
#define se second
#define mp(a, b) make_pair(a, b)
#define Endl putchar('\n')
#define mmset(a, b) memset(a, b, sizeof a)
// #define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<class T>inline T fab(T x){ return x<0? -x: x; }
template<class T>inline void getmin(T& x, const T rhs){ x=min(x, rhs); }
template<class T>inline void getmax(T& x, const T rhs){ x=max(x, rhs); }
template<class T>inline T readin(T x){
x=0; int f=0; char c;
while((c=getchar())<'0' || '9'<c) if(c=='-') f=1;
for(x=(c^48); '0'<=(c=getchar()) && c<='9'; x=(x<<1)+(x<<3)+(c^48));
return f? -x: x;
}
template<class T>inline void writc(T x, char s='\n'){
static int fwri_sta[1005], fwri_ed=0;
if(x<0) putchar('-'), x=-x;
do fwri_sta[++fwri_ed]=x%10, x/=10; while(x);
while(putchar(fwri_sta[fwri_ed--]^48), fwri_ed);
putchar(s);
}
}
using namespace Elaina;
const int Mod=20100713;
const int maxn=1e6;
inline int qkpow(int a, int n){
int ret=1;
for(; n>0; n>>=1, a=1ll*a*a%Mod)
if(n&1) ret=1ll*ret*a%Mod;
return ret;
}
int fac[maxn+5], n, k;
inline void prelude(){
fac[0]=1;
for(int i=1; i<=maxn; ++i)
fac[i]=1ll*fac[i-1]*i%Mod;
}
inline void solve(){
n=readin(1), k=readin(1);
if(k==0) return writc(1), void();
int ans=1ll*fac[k]*qkpow(k+1, n-k)%Mod;
ans=(ans+Mod-1ll*fac[k-1]*qkpow(k, n-k+1)%Mod)%Mod;
writc(ans);
}
signed main(){
prelude();
rep(_, 1, readin(1)) solve();
return 0;
}