xdoj 1067组合数学+动态规划 (一个题断断续续想了半年 233)

时间:2023-03-09 07:33:20
xdoj  1067组合数学+动态规划 (一个题断断续续想了半年 233)

xdoj  1067组合数学+动态规划 (一个题断断续续想了半年 233)

题目分析 : (8 4) 可以由(7 4),(6,4),( 4,4) 基础上转化

意味着一个新加入的元素可以按照它加入的方式分类,从而实现动态规划

核心:加入方式 新加入的元素构成转换环的元素个数(n的约数)

eg: (8,4) 新加入元素自己单独一个环 (7,4)

(6,4)新加入元素自己构成二元环 (6,4)

(4,4)新加入元素自己构成四元环 (4,4)

 #include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod=1e9+;
const int N=;
LL f[N],inv_f[N];// 阶乘和阶乘的逆元
LL dp[N];
LL p[N]; int cnt;
LL q_pow (LL x,LL k) {// 快速幂求逆元
LL ans=;
while (k) {
if (k&) ans=ans*x%mod;
x=x*x%mod;
k=k>>;
}
return ans;
}
LL c (int n,int m) {// 组合数c(n,m)
if (m>n) return ;
if (m>n-m) m=n-m;
LL x=inv_f[n-m]*inv_f[m]%mod;
return x*f[n]%mod;
}
int n,k;
int main ()
{
f[]=; dp[]=dp[]=;
for (int i=;i<N;i++) f[i]=i*f[i-]%mod;
inv_f[N-]=q_pow (f[N-],mod-);
for (int i=N-;i>=;i--) inv_f[i]=inv_f[i+]*(i+)%mod;
int T; scanf ("%d",&T);
while (T--) {
scanf ("%d %d",&n,&k);
LL sum=; int cnt=;
for (int i=;i<=k;i++)
if (k%i==) {
p[++cnt]=i;// 求得约数
}
for (int i=;i<=n;i++) {
dp[i]=;
for (int j=;j<=cnt;j++) {
if (i-p[j]<) break;
dp[i]=(dp[i]+c(i-,p[j]-)*f[p[j]-]%mod*dp[i-p[j]]%mod)%mod;
// c[i-1][p[j]-1] (选取p[j]-1个元素和新加入的元素构成p[j]元环)
// f[p[j]-1] p[j]个元素构成j元环的个数 (p[j]-1)!
// dp[i-p[j]] 剩余的( i-p[j])元素的组合个数
}
}
printf("%lld\n",dp[n]);
}
return ;
}