ADPC2-D 分配顏色

題意：

n*m的表格，一開始都是紅色的，現在可以進行p次操作1和q次操作2
操作1： 把某一行的同學進行取反操作：即紅色變為藍色，藍色變成紅色。
操作2： 把某一列的同學進行取反操作：即紅色變為藍色，藍色變成紅色。
問多少種方案滿足：執行完所有操作1和操作2之后，藍色恰好有t個
若兩個方案中的某一行或列被小A進行操作的次數不同時，則視為兩種不同的方案。

題解：

題目給的是取反操作，意味著成對的相同操作是相互抵消的，因為題目問有多少種方案滿足，我們可以這樣去設方案：設最終實際效果下有i行被翻轉，j列被翻轉，什么叫最終實際效果？有些行被翻之后又給翻回去了，那就不算被翻，我們要的是最終的呈現效果。
現在有i行j列是翻轉的，那么就有$i?m+j?n?2?i?j$(注意橫縱直線交界處是紅色而不是藍色)，如果$i?m+j?n?2?i?j=t$，且(p-i)和(q-j)都是偶數，說明這個情況是合法的，(p-i)和(q-j)是多余的操作，而多余的操作想要抵消就必須是偶數個才行。
我們就要考慮這個情況的合法方案：
很顯然我們可以從n中任意選i個翻轉，$C_n^i$
我們也可以從m中任意選j個翻轉，$C_n^j$
然后對于多余的操作p-i,我一開始想的是因為p-i一定是偶數，可以抵消，那么我們分配(p-i)/2就行，另一半部分跟著之前操作就行，那每次操作都可以選n個，那答案不就是$n^{(p?i)/2}$嗎？但并不是，因為題目說了不同的方案是指：某一行或列被小A進行操作的次數不同，而與操作順序無關，我們直接n的次冪求，會講不同順序的操作也看成不同操作，導致答案算多了。
那不gg了，并沒有，現在我們有(p-i)/2個操作要執行，每個操作可以選任意一行，且與順序無關，那問題轉換一下，有(p-i)/2個球，現在有n個盒子，現在要把球放在盒子里，隨機放，方案是多少？我們利用隔板法來做：現在有(p-i)/2+n個球，有n個盒子，每個盒子至少一個球，所有球排成一列，有(p-i)/2+n-1個間隙，在這些間隙中插入n-1個隔板，這樣就可以分出n個空間，相當于n個盒子，也就是$C_{(p?i)/2+n?1}^{n?1}$
列的也同理
詳細看代碼

代碼：

#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<queue> using namespace std; #define int long long const int mod=555555555; int C[4500][4500]; inline void init() {for(int i=0;i<4500;i++){for(int j=0;j<=i;j++){if(!j) C[i][j] = 1;else C[i][j] = (C[i-1][j] + C[i-1][j-1]) % mod;}} } signed main() {init();int n,m,p,q,t;cin>>n>>m>>p>>q>>t;long long ans=0;for(int i=0;i<=min(n,p);i++)for(int j=0;j<=min(m,q);j++){if((p-i)&1) continue;if((q-j)&1) continue;if(j*n+i*m-2*i*j==t){ ans+=C[n][i]*C[m][j]%mod*C[n+(p-i)/2-1][n-1]%mod*C[m+(q-j)/2-1][m-1]%mod;ans%=mod;}}printf("%lld",ans);return 0; } /* 10 10 200 200 0 */

總結

以上是生活随笔為你收集整理的ADPC2-D 分配颜色的全部內容，希望文章能夠幫你解決所遇到的問題。

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