wordpress 制作手机站,wordpress视频去广告插件下载地址,网站开发的几个主要阶段,西安微信公众号制作ADPC2-D 分配颜色
题意#xff1a;
n*m的表格#xff0c;一开始都是红色的#xff0c;现在可以进行p次操作1和q次操作2 操作1#xff1a; 把某一行的同学进行取反操作#xff1a;即红色变为蓝色#xff0c;蓝色变成红色。 操作2#xff1a; 把某一列的同学进行取反操作…ADPC2-D 分配颜色
题意
n*m的表格一开始都是红色的现在可以进行p次操作1和q次操作2 操作1 把某一行的同学进行取反操作即红色变为蓝色蓝色变成红色。 操作2 把某一列的同学进行取反操作即红色变为蓝色蓝色变成红色。 问多少种方案满足执行完所有操作1和操作2之后蓝色恰好有t个 若两个方案中的某一行或列被小A进行操作的次数不同时则视为两种不同的方案。
题解
题目给的是取反操作意味着成对的相同操作是相互抵消的因为题目问有多少种方案满足我们可以这样去设方案设最终实际效果下有i行被翻转j列被翻转什么叫最终实际效果有些行被翻之后又给翻回去了那就不算被翻我们要的是最终的呈现效果。 现在有i行j列是翻转的那么就有i∗mj∗n−2∗i∗ji*mj*n-2*i*ji∗mj∗n−2∗i∗j(注意横纵直线交界处是红色而不是蓝色)如果i∗mj∗n−2∗i∗jti*mj*n-2*i*jti∗mj∗n−2∗i∗jt且(p-i)和(q-j)都是偶数说明这个情况是合法的(p-i)和(q-j)是多余的操作而多余的操作想要抵消就必须是偶数个才行。 我们就要考虑这个情况的合法方案 很显然我们可以从n中任意选i个翻转CniC_{n}^iCni 我们也可以从m中任意选j个翻转CnjC_{n}^jCnj 然后对于多余的操作p-i,我一开始想的是因为p-i一定是偶数可以抵消那么我们分配(p-i)/2就行另一半部分跟着之前操作就行那每次操作都可以选n个那答案不就是n(p−i)/2n^{(p-i)/2}n(p−i)/2吗但并不是因为题目说了不同的方案是指某一行或列被小A进行操作的次数不同而与操作顺序无关我们直接n的次幂求会讲不同顺序的操作也看成不同操作导致答案算多了。 那不gg了并没有现在我们有(p-i)/2个操作要执行每个操作可以选任意一行且与顺序无关那问题转换一下有(p-i)/2个球现在有n个盒子现在要把球放在盒子里随机放方案是多少我们利用隔板法来做现在有(p-i)/2n个球有n个盒子每个盒子至少一个球所有球排成一列有(p-i)/2n-1个间隙在这些间隙中插入n-1个隔板这样就可以分出n个空间相当于n个盒子也就是C(p−i)/2n−1n−1C_{(p-i)/2n-1}^{n-1}C(p−i)/2n−1n−1 列的也同理 详细看代码
代码
#includecstdio
#includecstring
#includealgorithm
#includeiostream
#includequeue
using namespace std;
#define int long long
const int mod555555555;
int C[4500][4500];
inline void init()
{for(int i0;i4500;i){for(int j0;ji;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;cinnmpqt;long long ans0;for(int i0;imin(n,p);i)for(int j0;jmin(m,q);j){if((p-i)1) continue;if((q-j)1) continue;if(j*ni*m-2*i*jt){ ansC[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
*/
