题目描述
有一个(n)个元素的随机置换(P)，求(P)分解出的轮换个数的(m)次方的期望( imes n!)
(nleq 100000,mleq 30)
题解
解法一
有一种暴力的做法：设(f_{i,j})为(i)个元素的随机置换(P)，分解出的轮换个数的(j)次方的期望( imes i!)
考虑第(P_i)是什么。
如果是(i)，那么就多了一个轮换，用二项式定理展开得到(sum_{k=0}^jf_{i-1,k}inom{j}{k})。
如果不是(i)，那么可以看成把(i)插入到已有的轮换中，有(i-1)种方法，答案就是((i-1)f_{i-1,j})
处理出组合数直接DP即可。
时间复杂度：(O(nm^2))
解法二
考虑排列中轮换的个数为(i)的方案数，发现答案就是(egin{bmatrix}n\iend{bmatrix})。
推一波式子。
[egin{align}
ans&=sum_{i=1}^negin{bmatrix}n\iend{bmatrix}i^m\
&=sum_{i=1}^negin{bmatrix}n\iend{bmatrix}sum_{j=1}^megin{Bmatrix}m\jend{Bmatrix}inom{i}{j}j!\
&=sum_{i=1}^megin{Bmatrix}m\iend{Bmatrix}i!sum_{j=i}^negin{bmatrix}n\jend{bmatrix}inom{j}{i}\
&=sum_{i=1}^megin{Bmatrix}m\iend{Bmatrix}egin{bmatrix}n+1\i+1end{bmatrix}i!\
end{align}
]
最后这个式子是有组合意义的。
你要把 (n) 个元素分成 (j) 个环，然后选 (i) 个环出来。这个的方案数等价于先组出 (i) 个环，然后把剩下的元素放到一起，把所有元素的后继看成一个排列，那么组出剩下 (j-i) 个环的方案数就是元素个数的阶乘，即加上一个物品后组成一个环的方案数。
处理出斯特林数直接计算。
时间复杂度：(O(nm+m^2))
代码
解法一
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<utility>
#include<iostream>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
void open(const char *s)
{
#ifndef ONLINE_JUDGE
char str[100];
sprintf(str,"%s.in",s);
freopen(str,"r",stdin);
sprintf(str,"%s.out",s);
freopen(str,"w",stdout);
#endif
}
const ll p=1000000007;
ll f[100010][40];
ll fac[100010];
ll c[110][110];
int main()
{
int n,k;
scanf("%d%d",&n,&k);
for(int i=0;i<=k;i++)
{
c[i][0]=1;
for(int j=1;j<=i;j++)
c[i][j]=(c[i-1][j-1]+c[i-1][j])%p;
}
fac[0]=1;
for(int i=1;i<=n;i++)
fac[i]=fac[i-1]*i%p;
f[0][0]=1;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=k;j++)
for(int k=0;k<=j;k++)
f[i][j]=(f[i][j]+f[i-1][k]*c[j][k])%p;
for(int j=0;j<=k;j++)
f[i][j]=(f[i][j]+f[i-1][j]*(i-1))%p;
}
printf("%lld
",f[n][k]);
return 0;
}
解法二
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<utility>
#include<iostream>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int rd()
{
int s=0,c;
while((c=getchar())<'0'||c>'9');
s=c-'0';
while((c=getchar())>='0'&&c<='9')
s=s*10+c-'0';
return s;
}
void open(const char *s)
{
#ifndef ONLINE_JUDGE
char str[100];
sprintf(str,"%s.in",s);
freopen(str,"r",stdin);
sprintf(str,"%s.out",s);
freopen(str,"w",stdout);
#endif
}
const int p=1000000007;
int s[100010][32];
int S[31][31];
int main()
{
int n,m;
n=rd();
m=rd();
s[0][0]=1;
for(int i=1;i<=n+1;i++)
for(int j=1;j<=m+1;j++)
s[i][j]=(s[i-1][j-1]+ll(i-1)*s[i-1][j])%p;
S[0][0]=1;
for(int i=1;i<=m;i++)
for(int j=1;j<=m;j++)
S[i][j]=(S[i-1][j-1]+(ll)j*S[i-1][j])%p;
int ans=0;
int u=1;
for(int i=1;i<=m;i++)
{
u=(ll)u*i%p;
ans=(ans+(ll)u*S[m][i]%p*s[n+1][i+1])%p;
}
printf("%d
",ans);
return 0;
}