正題

題目鏈接:https://www.luogu.com.cn/problem/P4831

---

題目大意

$n?m$的網(wǎng)格上放置$2n$個炮，要求互不能攻擊。

數(shù)據(jù)滿足$n\le m\le 2000$或$n\le m\le 10^5$且$m?n\le 10$

---

解題思路

每行每列最多$2$個炮，所以模型可以轉換為求有多少種方案滿足：$1～n$的數(shù)字各兩個填在$m$個無序2元組（可以有空），并且每個組中的數(shù)互不相同。

直接硬鋼推式子很難做（好像可以推到生成函數(shù)那邊去），考慮一下巧妙的方法。

設$g(n,m)$表示$2n$個格子填下$1～m$中的數(shù)字各兩個的方案。這個的方案就是
$$g(n,m)=(2n)!\sum _{i=0}^{min\{n,m?n\}}\frac{\left(\genfrac{}{}{0ex}{}{m}{n?i}\right)\left(\genfrac{}{}{0ex}{}{m?n+i}{2i}\right)}{2^{n?i}}$$
表示$m$個數(shù)組中選出$n?i$對相同的來填，剩下的里面選出$2i$個單獨的來填，然后交換導致重復的情況有$2^{n?i}$種，要除去。

這個式子就和$m?n$有很大的關系了。

將這個式子和答案聯(lián)系起來，設$f(n,m)$表示答案，那么有
$$g(n,m)=\sum _{i=0}^n{2}^{n?i}\left(\genfrac{}{}{0ex}{}{n}{i}\right)P_m^{i}f(n?i,m?i)$$
因為$f(n,m)$是不同無序二元組，$\left(\genfrac{}{}{0ex}{}{n}{i}\right)P_m^i$表示$n$對中選出$i$個是相同的填入，剩下的都是不同的方案就是$f(n?i,m?i)$，然后因為$g$是統(tǒng)計有序二元組的，所以$2^n$表示隨意交換。

$$2^{n}f(n,m)=\sum _{i=0}^n\left(\genfrac{}{}{0ex}{}{n}{i}\right)P_m^{i}g(n?i,m?i)$$
$$f(n,m)=\frac{1}{2^n}\sum _{i=0}^n\left(\genfrac{}{}{0ex}{}{n}{i}\right)P_m^{i}g(n?i,m?i)$$

然后直接計算就好了，時間復雜度$O(n\times min\{n,m?n\})$

$Update:$修改了反演前的公式錯誤

---

code

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=2e5+10,P=998244353,inv2=(P+1)/2; ll n,m,fac[N],inv[N],pv2[N],ans; ll power(ll x,ll b){ll ans=1;while(b){if(b&1)ans=ans*x%P;x=x*x%P;b>>=1;}return ans; } ll C(ll n,ll m) {return fac[n]*inv[m]%P*inv[n-m]%P;} ll A(ll n,ll m) {return fac[n]*inv[n-m]%P;} ll g(ll n,ll m){ll ans=0;for(ll i=0;i<=min(n,m-n);i++)(ans+=C(m,n-i)*C(m-n+i,2*i)%P*pv2[n-i]%P)%=P;return ans*fac[2*n]%P; } signed main() {scanf("%lld%lld",&n,&m);inv[1]=1;for(ll i=2;i<N;i++)inv[i]=P-(P/i)*inv[P%i]%P;fac[0]=inv[0]=pv2[0]=1;for(ll i=1;i<N;i++)fac[i]=fac[i-1]*i%P,inv[i]=inv[i-1]*inv[i]%P,pv2[i]=pv2[i-1]*inv2%P;for(ll i=0,p=1;i<=n;i++,p=-p)(ans+=p*(g(n-i,m-i)*C(n,i)%P*A(m,i)%P))%=P;printf("%lld\n",(ans*pv2[n]%P+P)%P);return 0; }

總結

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

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