【NOI考前欢乐赛】小奇赏花

2016年6月26日1,3250
【题目背景】
桃之夭夭还绿了芭蕉

管他雨打风吹夜潇潇

花绽了新红也会凋

少年的心儿永不老

——《桃花笑》

【问题描述】

小奇的花园里有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 则需要是偶数,这样可以两两放一行,保证原来的行列 的技能次数奇偶性不变。