xdoj 1067 P-Function

这是一道数学题，意思是长度n的置换，问将该置换嵌套k次后不动的方案数。

因为置换可以分解为轮换，那么不动的方案轮换的大小肯定是k的因子。枚举k的因子d，下一步要确定这样长度d轮换有多少个，其余n-d个只需要递推求出。长度为d的轮换不是想当然的d个，也不是phi(d)个。想象这样的轮换构成环，第一个元素的指向有n-1种选择，第二个元素有n-2种选择，……，总个数为A(n-1,d-1)个。

再解释一下，算环的时候除以n而不是除以d，这是因为防止递推剩下n-d的时候同样大小的环被计重。

```
/*
```
```
Author: fffasttime
```
```
Date: 
```
```
*/
```
```
#include <bits/stdc++.h>
```
```
using namespace std;
```
```
typedef long long ll;
```
```
#define inc(i,n) for (int i=0;i<n;i++)
```
```
const int N=50010;
```
```
const ll P=1e9+7;
```
```
 
```
```
ll fac[N],ifac[N],dp[N];
```
```
 
```
```
ll qpow(ll a, ll x){
```
```
	ll ans=1;
```
```
	for (;x;a=a*a%P,x>>=1)
```
```
		if (x&1) ans=ans*a%P;
```
```
	return ans;
```
```
}
```

ll A(ll n, ll m){if (m==0) return 1;return fac[n]*ifac[n-m]%P;}

```
 
```
```
int d[N],dc;
```
```
 
```
```
int main(){
```
```
	fac[0]=ifac[0]=1;
```

	for (int i=1;i<N;i++) fac[i]=(fac[i-1]*i)%P;

	for (int i=1;i<N;i++) ifac[i]=qpow(fac[i],P-2);

```
	int T; cin>>T;
```
```
	while (T--){
```
```
		ll n,k; cin>>n>>k;
```
```
		int mf=sqrt(k);
```
```
		dc=0;
```
```
		memset(dp,0,sizeof dp);
```
```
		for (int i=1;i<=mf;i++) if (k%i==0){
```
```
			d[dc++]=i;
```
```
			if (i*i!=k) d[dc++]=k/i;
```
```
		}
```
```
		dp[0]=1;
```
```
		for (int i=1;i<=n;i++){
```
```
			for (int j=0;j<dc;j++)
```
```
				if (i-d[j]>=0)
```

					dp[i]+=dp[i-d[j]]*A(i-1,d[j]-1)%P,dp[i]%=P;

```
		}
```
```
		cout<<dp[n]<<'\n';
```
```
	}
```
```
	return 0;
```
```
}
```

发表评论 取消回复

发表评论取消回复