題目描述
桃之夭夭還綠了芭蕉
管他雨打風吹夜潇潇
花綻了新紅也會凋
少年的心兒永不老
——《桃花笑》
小奇的花園裡有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