2 条题解
-
0
gn的详解版：
#include<bits/stdc++.h> #define ll long long using namespace std; ll n,m,md=9999973,d[105][105][105],ans; int main(){ scanf("%lld %lld",&n,&m); d[0][0][m]=1;//d[i][j][k]->摆到第i行时,对于整个棋盘有j列最多还能放1个,有k列最多还能放2个 for(int i=1;i<=n;i++){ for(int j=0;j<=m;j++){ for(int k=0;k+j<=m;k++){ d[i][j][k]+=d[i-1][j][k];//此行不放 d[i][j][k]+=d[i-1][j+1][k]*(j+1);//上一次(j+1)个还能放1个的中任选一列放 if(j>=1)d[i][j][k]+=d[i-1][j-1][k+1]*(k+1);//上一次(k+1)个还能放2个的中任选一列放 d[i][j][k]+=d[i-1][j][k+1]*j*(k+1);//j的列和k的列各放一个 d[i][j][k]+=d[i-1][j+2][k]*(j+2)*(j+1)/2;//放两个j的列 if(j>=2)d[i][j][k]+=d[i-1][j-2][k+2]*(k+2)*(k+1)/2;//放两个k的列 d[i][j][k]%=md; if(i==n)ans+=d[i][j][k],ans%=md; } } }printf("%lld",ans); return 0; }zzh的纯享版：
//Code By zzh 2023.10.8 #include<bits/stdc++.h> #define LL long long using namespace std; const int mod=9999973; const int N=110; const LL inv=(mod/2)+1; LL f[N][N][N]; LL C(LL n) {return n*(n-1)*inv%mod;} int main() { int n,m; scanf("%d%d",&n,&m); f[0][0][0]=1; for(int i=1;i<=n;i++) { for(int j=0;j<=m;j++) { for(int k=0;k<=m-j;k++) { f[i][j][k]=f[i-1][j][k]; if(k>=1) f[i][j][k]=(f[i][j][k]+f[i-1][j+1][k-1]*(j+1))%mod; if(j>=1) f[i][j][k]=(f[i][j][k]+f[i-1][j-1][k]*(m-(j-1)-k))%mod; if(k>=1) f[i][j][k]=(f[i][j][k]+f[i-1][j][k-1]*j*(m-j-(k-1)))%mod; if(k>=2) f[i][j][k]=(f[i][j][k]+f[i-1][j+2][k-2]*C(j+2))%mod; if(j>=2) f[i][j][k]=(f[i][j][k]+f[i-1][j-2][k]*C(m-(j-2)-k))%mod; } } } LL ans=0; for(int i=0;i<=m;i++) for(int j=0;j<=m-i;j++) ans=(ans+f[n][i][j])%mod; printf("%lld\n",ans); return 0; } -
0
huangzheng
LV 6
@ 2025-10-8 16:51:56
gn的详解版：
#include<bits/stdc++.h> #define ll long long using namespace std; ll n,m,md=9999973,d[105][105][105],ans; int main(){ scanf("%lld %lld",&n,&m); d[0][0][m]=1;//d[i][j][k]->摆到第i行时,对于整个棋盘有j列最多还能放1个,有k列最多还能放2个 for(int i=1;i<=n;i++){ for(int j=0;j<=m;j++){ for(int k=0;k+j<=m;k++){ d[i][j][k]+=d[i-1][j][k];//此行不放 d[i][j][k]+=d[i-1][j+1][k]*(j+1);//上一次(j+1)个还能放1个的中任选一列放 if(j>=1)d[i][j][k]+=d[i-1][j-1][k+1]*(k+1);//上一次(k+1)个还能放2个的中任选一列放 d[i][j][k]+=d[i-1][j][k+1]*j*(k+1);//j的列和k的列各放一个 d[i][j][k]+=d[i-1][j+2][k]*(j+2)*(j+1)/2;//放两个j的列 if(j>=2)d[i][j][k]+=d[i-1][j-2][k+2]*(k+2)*(k+1)/2;//放两个k的列 d[i][j][k]%=md; if(i==n)ans+=d[i][j][k],ans%=md; } } }printf("%lld",ans); return 0; }
zzh的纯享版：//Code By zzh 2023.10.8 #include<bits/stdc++.h> #define LL long long using namespace std; const int mod=9999973; const int N=110; const LL inv=(mod/2)+1; LL f[N][N][N]; LL C(LL n) {return n*(n-1)*inv%mod;} int main() { int n,m; scanf("%d%d",&n,&m); f[0][0][0]=1; for(int i=1;i<=n;i++) { for(int j=0;j<=m;j++) { for(int k=0;k<=m-j;k++) { f[i][j][k]=f[i-1][j][k]; if(k>=1) f[i][j][k]=(f[i][j][k]+f[i-1][j+1][k-1]*(j+1))%mod; if(j>=1) f[i][j][k]=(f[i][j][k]+f[i-1][j-1][k]*(m-(j-1)-k))%mod; if(k>=1) f[i][j][k]=(f[i][j][k]+f[i-1][j][k-1]*j*(m-j-(k-1)))%mod; if(k>=2) f[i][j][k]=(f[i][j][k]+f[i-1][j+2][k-2]*C(j+2))%mod; if(j>=2) f[i][j][k]=(f[i][j][k]+f[i-1][j-2][k]*C(m-(j-2)-k))%mod; } } } LL ans=0; for(int i=0;i<=m;i++) for(int j=0;j<=m-i;j++) ans=(ans+f[n][i][j])%mod; printf("%lld\n",ans); return 0; }
- 1