zxh P102 c
【问题描述】
Hja特别有钱，他买了一个N×M的棋盘，然后Yjq到这个棋盘来搞事。一开始所有格子都是白的，Yjq进行R次行操作C次列操作，所谓一次操作，是将对应的行列上的所有格子颜色取反。现在Yjq希望搞事之后棋盘上有S个黑色格子，问Yjq有多少种搞事的方法 。
【输入格式】
第一行五个整数 N,M,R,C,S。
【输出格式】
一行个整数代表答案对10^9+7取模之后的值。
【样例输入】
2 4
【样例输出】
4
【数据规模与约定】
对于100%的数据，1≤N,M,R,C≤100000,0≤S≤N×M，有部分 。
题解
首先，对某一行或某一列进行两次操作是相当于没有操作的。
设行进行了x次操作，列进行了y次操作，黑格子数为mx+ny-2xy。
所以mx+ny-2xy=S。
枚举x，y=(S-mx)/(n-2x)。
行列各剩下R-x和C-y次操作，并且剩下操作必须为偶数次。
将(R-x)/2和(C-y)/2次操作分别放在n和m上。
方案数为C(n-1,(R-x)/2+n-1)* C(m-1,(C-y)/2+m-1)。
对于每个x，方案数为C(x,n)*C(y,m)*C(n-1,(R-x)/2+n-1)* C(m-1,(C-y)/2+m-1)。
注意：2x=n并且mx!=S的时候，y可以取任何值，要特殊讨论。
代码
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#define LL long long
using namespace std;
const int maxn=100010,mod=1000000007;
int n,m,r,c,ans;
int inv[maxn],v1[maxn],v2[maxn],v3[maxn],v4[maxn];
LL s;
int multi(LL a,int b){
a*=b;
if(a>=mod)a%=mod;
return (int)a;
}
void inc(int &a,int b){
a+=b;
if(a>=mod)a-=mod;
}
int mul(int a,int b){
int ans=1;
while(b){
if(b&1)ans=multi(ans,a);
a=multi(a,a);
b>>=1;
}
return ans;
}
int main(){
scanf("%d%d%d%d%lld",&n,&m,&r,&c,&s);
v1[0]=1;
for(int i=1;i<=100000;i++)
inv[i]=mul(i,mod-2);
int tmp=1;
for(int i=0;i<=(r>>1);i++){
v1[i]=tmp;
tmp=multi(tmp,multi(i+n,inv[i+1]));
}
tmp=1;
for(int i=0;i<=(c>>1);i++){
v2[i]=tmp;
tmp=multi(tmp,multi(i+m,inv[i+1]));
}
tmp=1;
for(int i=0;i<=n;i++){
v3[i]=tmp;
tmp=multi(tmp,multi(n-i,inv[i+1]));
}
tmp=1;
for(int i=0;i<=m;i++){
v4[i]=tmp;
tmp=multi(tmp,multi(m-i,inv[i+1]));
}
for(int i=r&1;i<=min(n,r);i+=2)
if(i*2!=n){
if(((s-(LL)i*m))%(n-i*2))continue;
int j=(int)((s-(LL)i*m)/(n-i*2));
if (j>c||j<0||((c-j)&1))continue;
int nowans=v3[i];
nowans=multi(nowans,v1[(r-i)>>1]);
nowans=multi(nowans,v4[j]);
nowans=multi(nowans,v2[(c-j)>>1]);
inc(ans,nowans);
}
else{
if((LL)i*m!=s)continue;
int nowans=v3[i];
nowans=multi(nowans,v1[(r-i)>>1]);
int cnt=0;
for(int j=(c&1);j<=min(r,c);j+=2)
inc(cnt,multi(v4[j],v2[(c-j)>>1]));
inc(ans,multi(nowans,cnt));
}
printf("%d
",ans);
return 0;
}