有几天没写题解了啊……
这几天在复习以前写过的题目。以后隔一阵子也要去看一看。
记忆化搜索大法好！
#include<cstdio>
#include<cstring>
const long long MOD=9999973;
long long n,m,f[105][105][105],c[105][105];
long long C(long long i,long long j){
if(j==0)return 1;
if(i==0)return 0;
if(i==1)return j==1?1:0;
if(j==1)return i;
if(c[i][j]!=-1)return c[i][j];
return c[i][j]=(C(i-1,j-1)%MOD+C(i-1,j)%MOD)%MOD;
}
long long dfs(long long a,long long b,long long c){
if(a>n)return 1;
if(f[a][b][c]!=-1)return f[a][b][c];
f[a][b][c]=dfs(a+1,b,c)%MOD;
if(c>=1){
f[a][b][c]=(f[a][b][c]+dfs(a+1,b+1,c-1)%MOD*c%MOD)%MOD;
}
if(m-b-c>=1){
f[a][b][c]=(f[a][b][c]+dfs(a+1,b,c+1)%MOD*(m-b-c)%MOD)%MOD;
f[a][b][c]=(f[a][b][c]+dfs(a+1,b+1,c)%MOD*(m-b-c)%MOD*c%MOD)%MOD;
}
if(c>=2){
f[a][b][c]=(f[a][b][c]+dfs(a+1,b+2,c-2)%MOD*C(c,2)%MOD)%MOD;
}
if(m-b-c>=2){
f[a][b][c]=(f[a][b][c]+dfs(a+1,b,c+2)%MOD*C(m-b-c,2)%MOD)%MOD;
}
return f[a][b][c];
}
int main(){
freopen("1801.in","r",stdin);
freopen("1801.out","w",stdout)
scanf("%lld %lld",&n,&m);
memset(f,-1,sizeof(f));
memset(c,-1,sizeof(c));
printf("%lld\n",dfs(1,0,0));
return 0;
}
评论 (0)
