Codeforces848D Shake It! -- DP
程序员文章站
2022-07-01 10:41:47
...
令
枚举
其中
然后考虑优化。
令
由调和级数可知,枚举
时间复杂度
代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 60
#define M 1000000007
inline void Add(int& x,int y){x=(x+y)%M;}
int i,j,k,n,m,p,q,f[N][N],g[N][N],F[N][N],t,inv[N];
int c;
int main(){
scanf("%d%d",&n,&m);
for(i=2,inv[0]=inv[1]=1;i<=n;i++)inv[i]=1ll*inv[M%i]*(M-M/i)%M;
f[0][1]=1;
for(i=1;i<=n;i++)
for(j=1;j<=i+1;j++){
for(p=0;p<=i-1;p++){
for(q=j;q<=p+1;q++)
Add(g[i][j],1ll*f[p][q]*f[i-1-p][j]%M);
for(q=j+1;q<=i-p;q++)
Add(g[i][j],1ll*f[p][j]*f[i-1-p][q]%M);
}
memset(F,0,sizeof(F));
for(k=0;k<=n;k++)
for(p=1;p<=k+1;p++){
c=1;
for(q=1;k+q*i<=n;q++){
c=1ll*c*(g[i][j]+q-1)%M*inv[q]%M;
Add(F[k+q*i][p+q*j],1ll*f[k][p]*c%M);
}
}
for(k=0;k<=n;k++)
for(p=1;p<=k+1;p++)
Add(f[k][p],F[k][p]);
}
cout<<f[n][m]<<endl;
return 0;
}
上一篇: 浅谈MySQL大表优化方案
下一篇: 银耳莲子羹的功效有哪些