江苏省交通建设厅门户网站,兰溪自适应网站建设特点,动漫制作,和卫通app下载题目链接 首先想到状压dp#xff0c;但是\(n,m\)高达100#xff0c;怎么压#xff1f; 容易发现#xff0c;每行每列最多两个象棋#xff0c;否则就直接gg了。 一个巧妙的设置状态的方式是#xff0c;只需要记录到当前行有多少列是放了1个炮和2个炮。 然后每一行有3种选择…题目链接 首先想到状压dp但是\(n,m\)高达100怎么压 容易发现每行每列最多两个象棋否则就直接gg了。 一个巧妙的设置状态的方式是只需要记录到当前行有多少列是放了1个炮和2个炮。 然后每一行有3种选择不放、放1个、放2个。分情况转移就行了。 #include cstdio
const int MOD 9999973;
const int MAXN 110;
int n, m, ans;
long long f[MAXN][MAXN][MAXN];
int C(int x){ //C(x,2)return x * (x - 1) / 2;
}
int main(){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; j k m; k){(f[i][j][k] f[i - 1][j][k]) % MOD; //不放(f[i][j 1][k] f[i - 1][j][k] * (m - j - k)) % MOD; //在没有棋子的列放1个if(j) (f[i][j - 1][k 1] f[i - 1][j][k] * j) % MOD; //在有棋子的列放1个(f[i][j 2][k] f[i - 1][j][k] * C(m - j - k)) % MOD; //在没有棋子的列放2个(f[i][j][k 1] f[i - 1][j][k] * (m - j - k) * j) % MOD; //一个放在有棋子的列一个放啊没有棋子的列if(j 1) (f[i][j - 2][k 2] f[i - 1][j][k] * C(j)) % MOD; //放2个在有棋子的列}for(int i 0; i m; i)for(int j 0; i j m; j)(ans f[n][i][j]) % MOD;printf(%d\n, ans);return 0;
} 转载于:https://www.cnblogs.com/Qihoo360/p/10918258.html
