炮

wjh15101051's space

卧薪尝胆，厚积薄发。

炮

Date: Thu Aug 23 16:13:45 CST 2018

In Category: NoCategory

Description：

在 $n\times m$ 的棋盘上放任意多个炮的方案数。

$1\le n,m \le 100$

Solution：

发现行与行，列与列之间可以交换，也就是说炮的具体位置是不用知道的，只用记录这一行中有多少列到现在为止还没放炮、放了一个炮、没放炮，转移时枚举放 $0,1,2$ 个炮预处理 $C_2^n$ 组合数分类讨论即可。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 110

#define MOD 999983

long long f[MAXN][MAXN][MAXN];

long long C[MAXN][2];

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 2;i < MAXN;++i)

	{

		C[i][2] = i * (i - 1) / 2;

		C[i][2] %= MOD;

	}

	f[0][0][0] = 1;

	for(int t = 1;t <= n;++t)

	{

		for(int i = 0;i <= m;++i)

		{

			for(int j = 0;j <= m - i;++j)

			{

				f[t][i][j] = (f[t][i][j] + f[t - 1][i][j]) % MOD;

				if(i >= 1)f[t][i][j] = (f[t][i][j] + f[t - 1][i - 1][j] * (m - j - (i - 1)) % MOD) % MOD;

				if(j >= 1)f[t][i][j] = (f[t][i][j] + f[t - 1][i + 1][j - 1] * (i + 1) % MOD) % MOD;

				if(j >= 2)f[t][i][j] = (f[t][i][j] + f[t - 1][i + 2][j - 2] * C[i + 2][2] % MOD) % MOD;

				if(i >= 1 && j >= 1)f[t][i][j] = (f[t][i][j] + f[t - 1][i][j - 1] * (m - (j - 1) - i) % MOD * i % MOD) % MOD;

				if(i >= 2)f[t][i][j] = (f[t][i][j] + f[t - 1][i - 2][j] * C[m - (i - 2) - j][2] % MOD) % MOD;

			}

		}

	}

	long long ans = 0;

	for(int i = 0;i <= m;++i)

	{

		for(int j = 0;j <= m - i;++j)

		{

			ans += f[n][i][j];

			ans %= MOD;

		}

	}

	cout << ans << endl;

	return 0;

}

In tag: DP-DP

wjh15101051