Description
有一個N*M的棋盤，初始每個格子都是白色的。
行操作是指選定某一行，將這行所有格子的顏色取反（黑白互換）。
列操作是指選定某一列，將這列所有格子的顏色取反。
XX進行了R次行操作C次列操作（可能對某行或者某列操作了多次），最后棋盤上有S個黑色格子。
問有多少種不同的操作方案。兩種操作方案不同，當且僅當對某行或者某列操作次數不同（也就是說與操作的順序無關）。
方案數可能很大，輸出它對10^9+7取模的結果。

Input
輸入只有5個整數N，M，R，C，S。

Output
輸出有且僅有一個整數，表示答案對10^9+7取模的結果。

Sample Input
2 2 2 2 4

Sample Output
4

Data Constraint
對于20%的數據，滿足N，M，R，C≤4。
對于60%的數據，滿足N，M，R，C≤1500。
對于100%的數據，滿足N，M，R，C≤100000，0≤S≤N*M。
.
.
.
.

分析

其實題目里面已經給了提示了，對于行和列操作，順序什么的是無所謂的，也就是說我們只需要考慮最終有幾行被翻轉了奇數次，幾列被翻轉了奇數次就可以統計答案了。
我們設有i行被翻轉了奇數次，j列被翻轉了奇數次，且最終有s個黑格，可以得到：
i*m+c*n-2*i*j=s(很好理解，有點類似于容斥，可自行模擬幾組看看)
于是我們可以依次枚舉i的值，就能對應的算出j的值。(當然i，j是有范圍的，細節見程序)
現在問題變成我們知道i、j，怎么統計方案數？

重新說明i的含義：對于n行，我們進行r次操作，有i行被操作了奇數次。

---

分成兩種情況(p=i,q=j)
1.

2*p=n，我們發現此時j的計算式的分母為0，這意味著此時j在范圍內隨意取值。注意此時s必須等于n*m/2(也請讀者模擬幾組數組，這是顯而易見的)
方案數calc1=C(n,p)*C((r-p)/2+n-1,n-1)*C(c+m-1,m-1)

2.

2*p<>n

方案數calc2=C(n,p)*C(m,q)*C((r-p)/2+n-1,n-1)*C((c-q)/2+m-1,m-1)

---

想必不能理解的形如C((r-p)/2+n-1,n-1)這樣的式子吧。
下面解釋它的含義：
我們有r次操作，最后有p點貢獻的，可以假設我們有r個球，每次我們可以把兩個球同時消去（稱為合并操作），最后我們還剩下p個球，這是因為對于一行進行兩次操作就相當于沒有操作。那么(r-p)/2就是我們合并操作的個數。在之后我們就可以任意把這(r-p)/2個操作分配給n行了，方案數就是C((r-p)/2+n-1,n-1)（每一次合并操作其實就是兩次翻轉）
.
.
.
.
.
.

程序：

#include<iostream> using namespace std;int mod=1000000007; int n,m,r,c,max1; long long s; int jie[200001],inv[200001];int work(int x,int y) {int ans=1;for (;y;y=y/2,x=1ll*x*x%mod)if (y&1) ans=1ll*ans*x%mod;return ans; } int h(int m,int n) {if (m<0||n<0||n>m) return 0;return 1ll*jie[m]*inv[n]%mod*inv[m-n]%mod; } void jb() {jie[0]=inv[0]=1;for (int i=1;i<=max1*2;i++) jie[i]=1ll*jie[i-1]*i%mod;for (int i=1;i<=max1*2;i++) inv[i]=1ll*inv[i-1]*work(i,mod-2)%mod; } int main() {int ans=0;cin>>n>>m>>r>>c>>s;max1=max(max(n,m),max(r,c));jb();for (int i=0;i<=min(n,r);i++){if (i*2==n) {if ((r-i)&1||s!=1ll*n*m/2) continue;ans=(ans+1ll*h(n,i)*h((r-i)/2+n-1,n-1)%mod*h(c+m-1,m-1)%mod)%mod; }else { if ((s-1ll*i*m)%(n-2*i)!=0) continue;int j=(s-1ll*i*m)/(n-2*i); if ((r-i)&1||(c-j)&1||j<0||j>c) continue;ans=(ans+1ll*h(n,i)*h(m,j)%mod*h((r-i)/2+n-1,n-1)%mod*h((c-j)/2+m-1,m-1)%mod)%mod;}}cout<<ans;return 0; }

轉載于:https://www.cnblogs.com/YYC-0304/p/9499932.html

總結

以上是生活随笔為你收集整理的【NOI2013模拟】棋盘游戏的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。