题目
考试时推到 p p p就嫌麻烦,不想推了。。。
讲真写好DP预处理调一年。
时间复杂度 O ( n 4 m 2 m ) O(n^4m2^m) O(n4m2m)的代码
T E ( b u t c o r r e t ) C o d e \mathrm {TE (but \ corret)\ Code} TE(but corret) Code
//#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define maxn 55
#define maxm 9
#define mod 258280327
#define rep(i,j,k) for(int i=(j),LIM=(k);i<=LIM;i++)
using namespace std;int n,m;
int P[maxm+1][1<<maxm][maxn][maxn],G[maxn][maxn][maxm+1],F[maxn][maxm+1],C[maxn][maxn][maxn][maxn];
int fac[maxn]={1,1},inv[maxn]={1,1},invf[maxn]={1,1},pw[maxn*maxm]={1,2};
int& upd(int &x){ return x+=x>>31&mod; }
int Pow(int b,int k){ int r=1;for(;k;k>>=1,b=1ll*b*b%mod) if(k&1) r=1ll*r*b%mod; return r; }
int Co(int a,int b){ return fac[a] * 1ll * invf[b] % mod * invf[a-b] % mod; }int main(){scanf("%d%d",&n,&m);int t1 = clock();rep(i,2,n) fac[i]=1ll*fac[i-1]*i%mod,inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod,invf[i]=1ll*invf[i-1]*inv[i]%mod;rep(i,0,n) rep(j,0,i) rep(u,0,n) rep(v,0,u) C[i][j][u][v] = Co(i,j) * 1ll * Co(u,v) % mod;rep(i,2,maxn*maxm-1)pw[i]=pw[i-1]*2ll%mod;rep(i,0,n) rep(j,0,n) P[0][0][i][j] = 1;int (*T)[maxn],(*R)[maxn],(*PT)[maxn];rep(i,1,m) rep(j,0,(1<<i-1)-1){T=P[i][j],R=P[i][j+(1<<i-1)],PT=P[i-1][j];rep(a,0,n) T[a][0] = T[0][a] = R[a][0] = R[0][a] = pw[a * i];rep(a,1,n) rep(b,1,n-a) { upd(R[a][b] = (2 * PT[a][b] - mod));rep(u,0,a) rep(v,0,b) T[a][b] = (T[a][b] + PT[u][v]* 1ll * PT[a-u][b-v] % mod * C[a][u][b][v]) % mod;G[a][b][i] = (G[a][b][i] + R[a][b] + (j ? T[a][b] : 0)) % mod;}}rep(j,1,m) rep(i,1,n) rep(a,0,i) F[i][j] = (F[i][j] + 1ll * Co(i,a) * (F[a][j-1]*1ll*pw[(j-1)*(i-a)]%mod + F[i-a][j-1]*1ll*pw[(j-1)*a]%mod + (a^i&&a^0?pw[i*(j-1)]*(1ll<<j-1)%mod + G[a][i-a][j-1]:0))) % mod;printf("%lld\n",1ll*F[n][m]*Pow(Pow(2,n*m),mod-2)%mod);
}
想过掉此题的可以写记忆化搜索。