這道題告訴我們推式子的時(shí)候頭要夠鐵。

題意

問一個(gè)\(n\times m\)的棋盤，擺上\(n\times 2\)個(gè)中國象棋的炮使其兩兩不能攻擊的方案數(shù)，對(duì)\(998244353\)取模。

\((n\leq m\leq 2000)或(n\leq m\leq 100000且m-n\leq 10)\)。

題解

怎么兩個(gè)數(shù)據(jù)范圍搞搞。

顯然合法方案等價(jià)于每行每列炮的數(shù)量不超過\(2\)，那么每一行就必定放\(2\)個(gè)炮了。

我們記\(f(n,m)\)為答案，考慮如何歸約到規(guī)模更小的問題。

那么我們枚舉最后一行炮的個(gè)數(shù)，分三類情況：

\(1\)、個(gè)數(shù)為\(0\)，歸約到\(f(n,m-1)\)。

\(2\)、個(gè)數(shù)為\(2\)（個(gè)數(shù)為\(1\)比較麻煩后面再說），那么先枚舉放在這一列的是哪兩行（\(\times \frac{n(n-1)}{2}\)），接著分類討論這兩行的另一個(gè)是否相同：

如果相同，則枚舉這是哪一個(gè)\((\times (m-1))\)，歸約到\(f(n-2,m-2)\)。

如果不同，則這兩行可以合并（同一行的唯一要求就是兩個(gè)列不同），只要根據(jù)有序性\(\times 2\)即可，于是歸約到\(f(n-1,m-1)\)。

\(3\)、個(gè)數(shù)為\(1\)，那么先枚舉占了最后一列的是哪一行\((\times n)\)，再枚舉這一行的另一個(gè)在哪一列\((\times (m-1))\)，問題就轉(zhuǎn)化為\(n-1\)行\(m-1\)列，其中有一列炮的個(gè)數(shù)\(\leq 1\)的方案數(shù)。

那么考慮容斥，用總方案數(shù)減去這一列放了兩個(gè)的方案數(shù)。前者就是\(f(n-1,m-1)\)，對(duì)于后者，進(jìn)行與情況\(2\)相似的討論，也可以進(jìn)行計(jì)算。

可以發(fā)現(xiàn)\(n>m\)時(shí)\(f(n,m)=0\)，于是復(fù)雜度就是\(O((m-n)n)\)。

代碼里為了方便我將\(m\)減去了\(n\)。

#include<cstdio> #include<cstring> const int mod=998244353,inv2=(mod+1)/2; inline int add(int a,int b) {return (a+=b)>=mod?a-mod:a; } inline int sub(int a,int b) {return (a-=b)<0?a+mod:a; } inline int mul(int a,int b) {return (long long)a*b%mod; } inline int qpow(int a,int b) {int res=1;for(;b;a=mul(a,a),b>>=1)if(b&1)res=mul(res,a);return res; } int n,m; namespace solver1 {const int N=2005;int memo[N][N];inline void init(){memset(memo,-1,sizeof(memo));memo[1][0]=0;memo[2][0]=1;memo[3][0]=6;return;}int f(int n,int m){if(m<0)return 0;if(n==0)return 1;if(~memo[n][m])return memo[n][m];int res=0;//0res=add(res,f(n,m-1));//1res=add(res,mul(mul(n,n+m-1),f(n-1,m)));if(n>=3)res=sub(res,mul(mul(n,n+m-1),mul(mul(mul(n-1,n-2),inv2),add(mul(n+m-2,f(n-3,m)),mul(2,f(n-2,m))))));//2if(n>=2)res=add(res,mul(mul(mul(n,n-1),inv2),add(mul(n+m-1,f(n-2,m)),mul(2,f(n-1,m)))));return memo[n][m]=res;}inline void main(){init();printf("%d\n",f(n,m-n));return;} } namespace solver2 {const int N=1e5+5;int memo[N][15];inline void init(){memset(memo,-1,sizeof(memo));memo[1][0]=0;memo[2][0]=1;memo[3][0]=6;return;}int f(int n,int m){if(m<0)return 0;if(n==0)return 1;if(~memo[n][m])return memo[n][m];int res=0;//0res=add(res,f(n,m-1));//1res=add(res,mul(mul(n,n+m-1),f(n-1,m)));if(n>=3)res=sub(res,mul(mul(n,n+m-1),mul(mul(mul(n-1,n-2),inv2),add(mul(n+m-2,f(n-3,m)),mul(2,f(n-2,m))))));//2if(n>=2)res=add(res,mul(mul(mul(n,n-1),inv2),add(mul(n+m-1,f(n-2,m)),mul(2,f(n-1,m)))));return memo[n][m]=res;}inline void main(){init();printf("%d\n",f(n,m-n));return;} } signed main() {scanf("%d%d",&n,&m);if(n<=2000&&m<=2000)solver1::main();elsesolver2::main();return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/Mr-Spade/p/10205848.html

總結(jié)

以上是生活随笔為你收集整理的洛谷P4831 Scarlet loves WenHuaKe的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。