欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Codeforces848D Shake It! -- DP

程序员文章站 2022-07-01 10:41:47
...

fi,j 表示 i 次操作后最小割为 j 的方案数。于是可以在 fi,j 的基础上选取 fa,bfc,d ,使 fa,bsfi,js 重合,fa,btfc,ds 重合,fc,dtfi,jt 重合。大概是这样:
Codeforces848D Shake It! -- DP
枚举 a,b,c,d,x,其中 x 表示使用次数,然后就可以转移了。

fi,j×(fa,bfc,d+x1x)fi+x(a+c+1),j+xmin(b,d)

其中 (fa,bfc,d+x1x) 表示从 fa,bfc,d 种方案中选取 x 种,可以重复的方案数。
然后考虑优化。
gp,q 表示  [a+c+1=p,min(b,d)=q]×fa,b×fc,d。由于 gp,q 只与 ip1fi,j 有关,可以枚举 i ,求出 gi,j ,再更新 f 数组。这样可以将转移的时间从 O(n4) 降到 O(n2)
由调和级数可知,枚举 x 的时间为 O(logn)
时间复杂度 O(n4logn)

代码

#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;
}
相关标签: codeforces dp