|
题目 #include<cstdio> #include<algorithm> using namespace std; #define N 200001 typedef long long LL; const int mod=1e9+7; LL inv[N],fac[N]; LL pow(LL a,int b) { LL res=1; for(;b;a=a*a%mod,b>>=1) if(b&1) res*=a,res%=mod; return res; } int main() { freopen('c.in','r',stdin); freopen('c.out','w',stdout); int n,m,r,c; LL s; scanf('%d%d%d%d%I64d',&n,&m,&r,&c,&s); fac[0]=1;inv[0]=1; for(int i=1;i<=max(n,m)+max(r,c);i++) fac[i]=i*fac[i-1],fac[i]%=mod,inv[i]=pow(fac[i],mod-2); int j; int ans=0; LL res; for(int i=(r&1);i<=min(r,n);i+=2) { if(n!=2*i) { if((s-1ll*i*m)%(n-2*i)) continue; j=(s-1ll*i*m)/(n-2*i); if(j<0 || j>min(c,m) || (c-j)&1) continue; res=fac[n]*inv[i]%mod*inv[n-i]%mod; res=res*fac[m]%mod*inv[j]%mod*inv[m-j]%mod; res=res*fac[n+(r-i>>1)-1]%mod*inv[n-1]%mod*inv[r-i>>1]%mod; res=res*fac[m+(c-j>>1)-1]%mod*inv[m-1]%mod*inv[c-j>>1]%mod; ans+=res; ans%=mod; //printf('%d %d %I64d\n',i,j,res); } } printf('%d',ans); } 解析： 解决本题关键： 假设有i行j列被翻了过来 那么可以得到等式 i*m+j*n-2*i*j=s 解得j=（s-i*m）/（n-2*i） 由此可知，我们只需要枚举i，就可以直接算出j 这个 i，j 合法的条件是： ① 不越界 ②（n-i）%2=0，（m-j）%2=0 因为只能再翻偶数次，才能保证当前i，j 合法 如何计算一对合法的i，j的答案？ n行里i行被翻了过来 C（n，i） m列里j列被翻了过来 C（m，j） 被翻了偶数次的行，就是把（r-i）/2 次机会 分给 n 行 C（（r-i）/2+n-1，n-1） 注意不是n行里面选 （r-i）/2 行翻过来，因为同一行可以不翻，也可以翻多次 同理，偶数次列为 C（（c-i）/2+m-1，m-1） 把这4个C 乘起来就是这一对i，j 的答案 最后累加所有的i，j 的贡献即可 本文解析作者：xxy |
|
|
