清北学堂模拟赛d4t6 c

分析：这道题比较有难度.

观察题目，发现只有当一行翻了奇数次后才会产生黑色格子，设有x行被翻了奇数次，y列被翻了偶数次，那么x*m + y*n - 2*x*y = s,接下来就要解方程了.对于二元一次方程，先枚举其中一个未知数x，就能推得y = (s - x*m)/(n - 2*x).假设翻了奇数次的x行y列各只用x,y次操作，那么接下来的任务就是把剩下的没用完的次数给分配出去，而且不能改变奇偶性.如果每一次操作是把一行或一列翻两次，那么就是要把(r - x)/2次操作分给n行，(c - y)/2次操作分给m列，这个的方案数可以用隔板法来求解，即:

C((r - x) / 2 + n - 1,n - 1),C((c - y) / 2 + m - 1,m - 1),n行m列中选x行y列的方案数为C(n,x),

C(m,y),那么答案就是C((r - x) / 2 + n - 1,n - 1)*C((c - y) / 2 + m - 1,m - 1)*C(n,x)*C(m,y).

统计方案数的时候要看y是不是整数，并且r-x和c-y要能被2整除.最后要特判一种情况：x*2=n,在这种情况下，无论多少列被染了奇数次黑色格子永远是那么多，把所有列的情况算一次就好了.

以后取模运算要单独开一个函数写，这样不容易错.

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

const int mod = 1e9 + , maxn = ;

using namespace std;

long long p[maxn];

int n, m, r, c;

long long s, v1[maxn], v2[maxn], v3[maxn], v4[maxn], ans;

long long mul(long long a, long long b)

{

    a *= b;

    if (a >= mod)

        a %= mod;

    return a;

}

void inc(long long &a, long long b)

{

    a += b;

    if (a >= mod)

        a -= mod;

}

long long qpow(long long a, long long b)

{

    long long res = ;

    while (b)

    {

        if (b & )

            res = mul(res, a);

        b >>= ;

        a = mul(a, a);

    }

    return res;

}

int main()

{

    scanf("%d%d%d%d%lld", &n, &m, &r, &c, &s);

    p[] = ;

    for (int i = ; i <= ; i++) //逆元

        p[i] = ((mod - mod / i) * p[mod % i]) % mod;

    long long temp = ;

    for (int i = ; i <= r; i++)  //求C(n + i - 1,n - 1)

    {

        v1[i] = temp;

        temp = mul(temp, mul(i + n, p[i + ]));

    }

    temp = ;

    for (int i = ; i <= c; i++)

    {

        v2[i] = temp;

        temp = mul(temp, mul(i + m, p[i + ]));

    }

    temp = ;

    for (int i = ; i <= n; i++)

    {

        v3[i] = temp;

        temp = mul(temp, mul(n - i, p[i + ]));

    }

    temp = ;

    for (int i = ; i <= m; i++)

    {

        v4[i] = temp;

        temp = mul(temp, mul(m - i, p[i + ]));

    }

    for (long long i = r & ; i <= min(n, r); i += )

    {

        if (i *  != n)

        {

            if (((s - (long long)m * i)) % (n - i * ))

                continue;

            long long b = (s - (long long)i * m) / (n - i * );

            if (b > c || b <  || (c - b) & )

                continue;

            long long temp = v3[i];

            temp = mul(temp, v1[(r - i) >> ]);

            temp = mul(temp, v4[b]);

            temp = mul(temp, v2[(c - b) >> ]);

            inc(ans, temp);

        }

        else

        {

            if ((long long)i * m != s)

                continue;

            long long temp = v3[i];

            temp = mul(temp, v1[(r - i) >> ]);

            long long cnt = ;

            for (int b = (c & ); b <= min(r, c); b += )

                inc(cnt, mul(v4[b], v2[(c - b) >> ]));

            inc(ans, mul(temp, cnt));

        }

    }

    printf("%lld\n", ans);

    return ;

}