「NOI考前欢乐赛」小奇赏花
管他雨打风吹夜潇潇
花绽了新红也会凋
少年的心儿永不老
——《桃花笑》
「问题描述」
小奇的花园里有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。
题解
原题「East!_XVI」皮城女警
出题人18357：
我们发现如果确定有多少行是奇数次[和平使者],多少列是奇数次 [和平使者],那么奇点个数就确定了!
所以设有 x 个奇行,y 个奇列,然后 S=x(m-y)+(n-x)y,枚举 x,则 y=(S-xm)/(n-2x),这样可以算出 y,注意定义域。 然后对于每对可行的(x,y),x 有 C(n,x)种放法,y 有 C(m,y)种放法, 剩下的 R 和 C 则需要是偶数,这样可以两两放一行,保证原来的行列 的技能次数奇偶性不变。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #define pa pair<int,int> #define ll long long #define mod 1000000007 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } ll n,m,r,c,s,ans; ll fac[200005],ine[200005],f[200005]; void pre() { ine[1]=1; for(int x=2;x<=200000;x++) { ll a=mod/x,b=mod%x; ine[x]=(-a*ine[b]%mod+mod)%mod; } } ll C(ll a,ll b) { if(b==0)return 1; return fac[a]*f[a-b]%mod*f[b]%mod; } void solve(ll a,ll b) { if(b<0||b>c||b>m)return; if((r-a)&1||(c-b)&1)return; ll t1=(r-a)/2,t2=(c-b)/2; ll tot=C(n,a)*C(m,b)%mod; if(b==0)tot=tot*C(n+t1-1,n-1)%mod*C(m+c-1,m-1)%mod; else tot=tot*C(n+t1-1,n-1)%mod*C(m+t2-1,m-1)%mod; ans=(ans+tot)%mod; } int main() { fac[0]=1;for(int i=1;i<=200000;i++)fac[i]=fac[i-1]*i%mod; pre(); f[0]=1;for(int i=1;i<=200000;i++)f[i]=f[i-1]*ine[i]%mod; n=read();m=read();r=read();c=read();s=read(); for(int a=0;a<=r&&a<=n;a++) if(n-2*a==0) { if(a*m==s&&c%2==0) { solve(a,0); continue; } } else if((s-a*m)%(n-2*a)==0) solve(a,(s-a*m)/(n-2*a)); cout<<ans<<endl; return 0; } |
Subscribe
计数器 9786017
OI 课件=>
OI 课件=>