题目描述
桃之夭夭还绿了芭蕉
管他雨打风吹夜潇潇
花绽了新红也会凋
少年的心儿永不老
——《桃花笑》
小奇的花园里有n行m列棵桃花树，花色各不相同。小奇漫步在花园中，有时它觉得某一行/列的桃花很美，便会在这一整行/列的每棵树下捡一枚花瓣，到了傍晚，他发现自己选择了r行c列（同一行/列可能被选择不止一次）的花瓣。
回家之后，小奇发现：有s种颜色的花瓣数为奇数，他想知道，有多少种选择方案能有这样的效果呢？
（两种方案不同当且仅当某行/列被选择的次数不同）
输入
第一行包括5个整数，n，m，r，c，s。
输出
输出一个整数表示答案（mod 1000000007）。
样例输入
2 2 2 2 4
样例输出
4
提示
对于 20% 的数据, n，m ≤ 4，r，c ≤ 4；
对于 50% 的数据, n，m ≤ 500，r，c ≤ 2000； 对于另外 10% 的数据, n，m ≤ 100000，s = n * m；
对于 100% 的数据, n，m ≤ 100000，r，c ≤ 100000，s ≤ 10^12。
发现，如果确定有多少行是奇数行，有多少列是奇数列，那么就可以求得有多少点是奇数点。
所以设有 x 个奇行,y 个奇列,然后 S=x(m-y)+(n-x)y,枚举 x,则 y=(S-xm)/(n-2x),这样可以算出 y,（注意当n-2x==0时，在s-xm==0时这方程有无数解）
此时我们就知道了x行为奇数行，y列为奇数列，这些行列排布的方案数为C(n,x)*C(m,y)
对每一种方案数，以行为例，r个物品，x行放奇数个，n-x行放偶数个，可以为空。我们先再x行上每行放1个，剩下的两个一组去放，就可以实现上述要求。即方案数为C((r-x)/2+n-1,n-1)。 #include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const int N=2e5+50;
const int p=1e9+7;
ll n,m,r,c,s,ans;
ll fac[N],ine[N],f[N];
ll poww(ll x,ll y,int p)
{
ll ret=1,tt=x;
while(y)
{
if (y&1) ret=(ret*tt)%p;
tt=(tt*tt)%p;
y>>=1;
}
return ret;
}
void pre()
{
fac[0]=1;for(int i=1;i<=200000;i++)fac[i]=fac[i-1]*i%p;
ine[1]=1;
for(int x=2;x<=200000;x++)
{
ll a=p/x,b=p%x;
ine[x]=(-a*ine[b]%p+p)%p;
}
f[0]=1;for(int i=1;i<=200000;i++)f[i]=f[i-1]*ine[i]%p;
}
ll C(ll a,ll b)
{
if(b==0)return 1;
return fac[a]*f[a-b]%p*f[b]%p;
}
void cal(ll x,ll y)
{
// cout<<x<<' '<<y<<endl;
if ((r-x)%2||(c-y)%2) return; //剩余的行和列需要为偶数次
ll t1=(r-x)/2,t2=(c-y)/2; //两两结合保证奇偶性
ll cnt=C(n,x)*C(m,y)%p; //行和列的选择方案
cnt=cnt*C(t1+n-1,n-1)%p*C(t2+m-1,m-1)%p;
ans=(ans+cnt)%p;
}
int main()
{
// freopen("Caitlyn_7.in","r",stdin);
scanf("%lld%lld%lld%lld%lld",&n,&m,&r,&c,&s);
pre();
for (ll x=0;x<=r&&x<=n;x++)
{
if (n-2*x==0) //被除数是0
{
if (x*m==s) //系数是0
{
for (int i=0;i<=m;i++) cal(x,i); //y取任意值
}
}
else if((s-x*m)%(n-2*x)==0)
{
ll y=(s-x*m)/(n-2*x);
if (y>=0&&y<=c&&y<=m) cal(x,y);
}
}
printf("%lld\n",ans);
// fclose(stdin);
return 0;
} View Code
转载于:https://www.cnblogs.com/tetew/p/9395908.html