题目描述
这次小可可想解决的难题和中国象棋有关,在一个 nn 行 mm 列的棋盘上,让你放若干个炮(可以是 00 个),使得没有一个炮可以攻击到另一个炮,请问有多少种放置方法。大家肯定很清楚,在中国象棋中炮的行走方式是:一个炮攻击到另一个炮,当且仅当它们在同一行或同一列中,且它们之间恰好 有一个棋子。你也来和小可可一起锻炼一下思维吧!
输入格式
一行包含两个整数 n,mn,m,之间由一个空格隔开。
输出格式
总共的方案数,由于该值可能很大,只需给出方案数模 99999739999973 的结果。
输入输出样例
输入 #1复制
1 3
输出 #1复制
7
说明/提示
样例说明
除了 33 个格子里都塞满了炮以外,其它方案都是可行的,所以一共有 2 \times 2 \times 2-1=72×2×2−1=7 种方案。
数据规模与约定
- 对于 30\%30% 的数据,nn 和 mm 均不超过 66。
- 对于 50\%50% 的数据,nn 和 mm 至少有一个数不超过 88。
- 对于 100\%100% 的数据,1 \leq n,m \leq 1001≤n,m≤100。
思路:因为能攻击到的情况是同行同列两个炮中间隔了一个炮的情况
也就是有三个炮在同一行或者同一列
那么我们就让他一行和一列就只能有0 1 2个炮
dp[i][j][k]表示前i行有j列放了1个炮,有k列放了两个炮
首先第i行不放的话:dp[i][j][k]=dp[i-1][j][k]
第i行放一个:
1.放在有0个炮的列上:dp[i][j][k]+=dp[i-1][j-1][k]*(m-j-k+1)
(因为我们放在了有0个炮的列上之后的状态是 j k,j比原来多了一个,k不变那么i-1行的状态就是dp[i][j-1][k])
2.放在有1个炮的列上:dp[i][j][k]+=dp[i-1][j+1][k-1]*(j+1)
第i行放两个:
1.都放在有0个棋子的列:dp[i][j][k]+=dp[i-1][j-2][k]*getc(m-k-j+2,2,9999973);
2.都放在有1个棋子的列:dp[i][j][k]+=dp[i-1][j+2][k-2]*getc(j+2,2,9999973)
3.一个放在有0个的一个放在有一个的:dp[i][j][k]+=dp[i-1][j][k-1]*j*(m-j-k+1)
最后的答案是所有在前n行,有0~m个列放了1个,有0~m-j列放了两个的方法的总和
/*.----------------. .----------------. .----------------. .----------------.
| .--------------. || .--------------. || .--------------. || .--------------. |
| | ________ | || | _________ | || | ____ ____ | || | ____ | |
| | |_ ___ `. | || | |_ ___ | | || ||_ \ / _|| || | .' `. | |
| | | | `. \ | || | | |_ \_| | || | | \/ | | || | / .--. \ | |
| | | | | | | || | | _| _ | || | | |\ /| | | || | | | | | | |
| | _| |___.' / | || | _| |___/ | | || | _| |_\/_| |_ | || | \ `--' / | |
| | |________.' | || | |_________| | || ||_____||_____|| || | `.____.' | |
| | | || | | || | | || | | |
| '--------------' || '--------------' || '--------------' || '--------------' |'----------------' '----------------' '----------------' '----------------'*/
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<deque>
#include<cmath>
#include<stack>
#define int long long
#define lowbit(x) x&(-x)
#define PI 3.1415926535
#define endl "\n"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int gcd(int a,int b) {return b? gcd(b,a%b):a;
}
/*
int dx[8]={-2,-2,-1,1,2,2,-1,1};
int dy[8]={-1,1,2,2,1,-1,-2,-2};
int dx[4]={0,-1,0,1};
int dy[4]={-1,0,1,0};
int dx[8]={-1,1,0,0,-1,-1,1,1};
int dy[8]={0,0,-1,1,-1,1,-1,1};
*/
//int e[N],ne[N],h[N],idx,w[N];
/*void add(int a,int b,int c){e[idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx++;
}
*/
const int N=100+10;
int m,p,n;
int dp[N][N][N];
int ksm(int a,int b,int mod){int res=1%mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;
}
int c(int a,int b,int mod){if(b>a)return 0;int res=1;for(int i=a,j=1;j<=b;j++,i--){res=res*i%mod;res=res*ksm(j,mod-2,mod)%mod;}return res;
}
int getc(int a,int b,int mod){if(a<mod&&b<mod)return c(a,b,mod);else return c(a%mod,b%mod,mod)*getc(a/mod,b/mod,mod)%mod;
}
void sove(){cin>>n>>m;p=9999973;dp[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++){dp[i][j][k]=dp[i-1][j][k];//不放dp[i][j][k]%=p;//放一个棋子if(j>=1)dp[i][j][k]+=dp[i-1][j-1][k]*(m-j-k+1);//放在有0个棋子的列dp[i][j][k]%=p;if(k>=1)dp[i][j][k]+=dp[i-1][j+1][k-1]*(j+1);//放在有一个棋子的列dp[i][j][k]%=p;//放两个if(j>=2)dp[i][j][k]+=dp[i-1][j-2][k]*getc(m-k-j+2,2,9999973);//都放在有0个棋子的列dp[i][j][k]%=p;if(k>=2)dp[i][j][k]+=dp[i-1][j+2][k-2]*getc(j+2,2,9999973);//都放在有1个棋子的列dp[i][j][k]%=p;if(k>=1)dp[i][j][k]+=dp[i-1][j][k-1]*j*(m-j-k+1);//一个放在有0个的一个放在有一个的dp[i][j][k]%=p;}}}int ans=0;for(int i=0;i<=m;i++){for(int j=0;j+i<=m;j++){ans=(ans+dp[n][i][j])%p;}}cout<<ans<<endl;
}signed main(){ios::sync_with_stdio(false);cin.tie() ,cout.tie() ;int t=1;
// cin>>t;while(t--){sove();}return 0;
}