luogu 2051 [AHOI2009]中国象棋

---

真是一道令人愉♂悦丧心并框的好题。。。

首先“没有一个炮可以攻击到另一个炮”有个充分条件就是没有三个炮在同一行或同一列。证明：显然。

所以每行/每列最多2个炮。

还有一个点就是任意交换行和列不会改变这个方案的可行性。

那么可以脑补摆完前i行之后就把所有列排个序，会有摆了1个的列，摆了2个的列和没摆的列。

如果是桶排，就记录一下每个有多少就行了。

所以需要3个桶。可以省掉一个，因为知道了总共m列。

那么设f[i][j][k]为摆完了前i行，且j列摆了1个炮，k列摆了2个炮，你摆放的总方案数，然后滚动一下第一维

然后很多种情况，有注释。

PS.要多取膜！！！被坑到了

// It is made by XZZ

#include<cstdio>

#include<cstring>

#include<algorithm>

#define Fname "cchess"

using namespace std;

#define rep(a,b,c) for(rg int a=b;a<=c;a++)

#define drep(a,b,c) for(rg int a=b;a>=c;a--)

#define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])

#define il inline

#define rg register

#define vd void

typedef long long ll;

#define mod 9999973

il int gi(){

    rg int x=0;rg bool flg=0;rg char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')flg=1;ch=getchar();}

    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();

    return flg?-x:x;

}

ll f[2][101][101];

il vd add(ll&a,ll b){a+=b;if(a>=mod)a-=mod;}

int main(){

#ifdef xzz

	freopen(Fname".in","r",stdin);

	freopen(Fname".out","w",stdout);

#endif

	int n=gi(),m=gi(),now=1;

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

	rg ll t;

	rep(i,0,n-1){

		now^=1;

		memset(f[now^1],0,sizeof f[now^1]);

		drep(j,m,0)drep(k,m-j,0)if(f[now][j][k]){

			t=(f[now][j][k]%=mod);

			//第i行

			add(f[now^1][j][k],t);//不放

			add(f[now^1][j+1][k],t*(m-j-k)%mod);//放一个 新占一列

			if(j)add(f[now^1][j-1][k+1],t*j%mod);//放一个 与一列放了一个的放一起

			if(m-j-k>1)add(f[now^1][j+2][k],t*(m-j-k)*(m-j-k-1)/2%mod);//放两个 新占两列

			if(j&&m-j-k>0)add(f[now^1][j][k+1],t*(m-j-k)*j%mod);//放两个 一个新占一列 另一个与一列放了一个的放一起

			if(j>1)add(f[now^1][j-2][k+2],t*j*(j-1)/2%mod);//放两个 都与一列放了一个的放一起

		}

	}

	ll ans=0;

	now^=1;

	rep(i,0,m)rep(j,0,m-i)add(ans,f[now][i][j]);

	printf("%lld\n",ans);

	return 0;

}