2022年9月月赛乙组 T3.棋盘问题
内存限制: 256 Mb时间限制: 1000 ms
题目描述
给定一个 n×m 的棋盘,在上面放置若干个棋子,要求任一行任一列至多只能有两颗棋子,求一共有多少种放置方案。
由于方案数可能会很大,对方案数模 10^9+7。一只棋子都不放也算一种方案。
输入格式
两个整数表示 n 与 m
输出格式
单个整数:表示方案数模 10^9+7
数据范围
对于 20% 的数据,1≤n,m≤10
对于 100% 的数据,1≤n,m≤100
样例数据
输入:
2 3
输出:
49
输入:
1 3
输出:
7
题目解析:状态DP 分类讨论
- #include
- using namespace std;
- const int P=1e9+7;
- long long dp[2][101][101][101];//滚动数组 做空间优化
- int main()
- {
- int n,m;
- cin>>n>>m;
- //初始化dp[0]
- for(int x=0;x<=m;x++){
- for(int y=0;y<=m;y++){
- if(x+y>m) break;
- int z=m-x-y;
- dp[0][x][y][z]=1;
- }
- }
- //从dp[1]到dp[n]
- for(int i=1;i<=n;i++){
- for(int x=0;x<=m;x++){
- for(int y=0;y<=m;y++){
- if(x+y>m) break;
- int z=m-x-y;
- if(y+2*z>2*(n-i)) continue;
- int _i=i&1;
- int _isub1=(i-1)&1;
- //分类讨论:
- //1)第i行用了0个1 dp[i-1][x][y][z]
- dp[_i][x][y][z]=dp[_isub1][x][y][z];
- //2)第i行用了1个1 dp[i-1][x-1][y+1][z],dp[i-1][x][y-1][z+1]
- if(x) dp[_i][x][y][z]+=x*dp[_isub1][x-1][y+1][z];
- if(y) dp[_i][x][y][z]+=y*dp[_isub1][x][y-1][z+1];
- //3)第i行用了2个1
- if(x>1) dp[_i][x][y][z]+=x*(x-1)/2*dp[_isub1][x-2][y+2][z];
- if(y>1) dp[_i][x][y][z]+=y*(y-1)/2*dp[_isub1][x][y-2][z+2];
- if(x&&y) dp[_i][x][y][z]+=y*x*dp[_isub1][x-1][y][z+1];
- dp[_i][x][y][z]%=P;
-
- }
- }
- }
- //输出dp[n][m][0][0]
- cout<
1][m][0][0]; - return 0;
- }