题目分析 ： （8 4） 可以由（7 4），（6，4），（ 4，4） 基础上转化
意味着一个新加入的元素可以按照它加入的方式分类，从而实现动态规划
核心：加入方式 新加入的元素构成转换环的元素个数（n的约数）
eg: （8，4） 新加入元素自己单独一个环 （7，4）
（6，4）新加入元素自己构成二元环 （6，4）
（4，4）新加入元素自己构成四元环 （4，4）
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 const LL mod=1e9+7; 5 const int N=20007; 6 LL f[N],inv_f[N];// 阶乘和阶乘的逆元 7 LL dp[N]; 8 LL p[N]; int cnt; 9 LL q_pow (LL x,LL k) {// 快速幂求逆元 10 LL ans=1; 11 while (k) { 12 if (k&1) ans=ans*x%mod; 13 x=x*x%mod; 14 k=k>>1; 15 } 16 return ans; 17 } 18 LL c (int n,int m) {// 组合数c(n,m) 19 if (m>n) return 0; 20 if (m>n-m) m=n-m; 21 LL x=inv_f[n-m]*inv_f[m]%mod; 22 return x*f[n]%mod; 23 } 24 int n,k; 25 int main () 26 { 27 f[0]=1; dp[0]=dp[1]=1; 28 for (int i=1;i<N;i++) f[i]=i*f[i-1]%mod; 29 inv_f[N-1]=q_pow (f[N-1],mod-2); 30 for (int i=N-2;i>=0;i--) inv_f[i]=inv_f[i+1]*(i+1)%mod; 31 int T; scanf ("%d",&T); 32 while (T--) { 33 scanf ("%d %d",&n,&k); 34 LL sum=0; int cnt=0; 35 for (int i=1;i<=k;i++) 36 if (k%i==0) { 37 p[++cnt]=i;// 求得约数 38 } 39 for (int i=2;i<=n;i++) { 40 dp[i]=0; 41 for (int j=1;j<=cnt;j++) { 42 if (i-p[j]<0) break; 43 dp[i]=(dp[i]+c(i-1,p[j]-1)*f[p[j]-1]%mod*dp[i-p[j]]%mod)%mod; 44 // c[i-1][p[j]-1] （选取p[j]-1个元素和新加入的元素构成p[j]元环） 45 // f[p[j]-1] p[j]个元素构成j元环的个数 （p[j]-1)! 46 // dp[i-p[j]] 剩余的（ i-p[j])元素的组合个数 47 } 48 } 49 printf("%lld ",dp[n]); 50 } 51 return 0; 52 }