NOI模拟题4 Problem C: 填格子(board)

Solution

首先我们要有敏锐的直觉: 我们将每一列中不选哪种颜色看作是一个序列, 则我们发现这个序列要求相邻两位的颜色不同. 我们还发现, 一个这样的序列对应两种不同的合法的棋盘, 因此统计合法棋盘数的问题, 就转化为了统计合法序列数.

我们不妨设(R > G > B). 我们可以用R将这个序列切成(R - 1)或(R)或(R + 1)段, 这取决于序列的开头/结尾是否放R. 一旦确定了序列开头和结尾是否放R, 我们在后面就只考虑在序列中间放R, 而不考虑开头和结尾. 每一段由G和B交错组成. 我们将这些由G和B组成的段分为以下三类:

GBGBGB...GB 或 BGBGBG...BG, 即B的个数与G的个数相同. 我们记这样的段有(x)段.
GBGB...GBG, 即G的个数比B多(1). 我们记这样的段有(y)段.
BGBG...BGB, 即B的个数比G多1. 我们记这样的段有(z)段.

则我们发现(y - z)的值是固定的: (y - z = G - B).

我们假设(R)将该序列分为(d)段(根据前文, (或或d = R - 1或d = R + 1或d = R)), 则(x + y + z = d). 我们再枚举(x), 则(y)与(z)的数量也被确定了. 我们把第二和第三种情况的序列补全为G和B数量相等的情况, 则现在我们总共有(frac{G + B + y + z}{2})对GB或BG.

我们用插板法在这些BG或GB中插入(d - 1)个R即可.

#include <cstdio>
#include <algorithm>

using namespace std;
const int M = (int)1e6, MOD = (int)1e9 + 7;
int pw[M + 1], fac[M + 1], facInv[M + 1];
inline int C(int a, int b)
{
    if (a < b) return 0;
    return (long long)fac[a] * facInv[a - b] % MOD * facInv[b] % MOD;
}
inline int getInverse(int a)
{
    int res = 1;
    for (int x = MOD -  2; x; a = (long long)a * a % MOD, x >>= 1) if (x & 1) res = (long long)res * a % MOD;
    return res;
}
inline int work(int d, int x, int y)
{
    int ans = 0;
    for (int a = 0; a <= d - (x - y); ++ a) if (((d - a) - (x - y)) % 2 == 0)
    {
        int c = ((d - a) - (x - y)) / 2, b = x - y + c;
        ans = (ans + (long long)C((x + y + b + c) / 2 - 1, d - 1) * C(d, a) % MOD * C(b + c, b) % MOD * pw[a] % MOD) % MOD;
    }
    return ans;
}
int main()
{

#ifndef ONLINE_JUDGE

    freopen("board.in", "r", stdin);
    freopen("board.out", "w", stdout);

#endif

    pw[0] = 1; for (int i = 1; i <= M; ++ i) pw[i] = pw[i - 1] * 2 % MOD;
    fac[0] = facInv[0] = 1; for (int i = 1; i <= M; ++ i) fac[i] = (long long)fac[i - 1] * i % MOD, facInv[i] = getInverse(fac[i]);
    int T; scanf("%d", &T);
    for (int cs = 0; cs < T; ++ cs)
    {
        int m, R, G, B; scanf("%d%d%d%d", &m, &R, &G, &B);
        R = m - R; G = m - G; B = m - B;
        if (G < B) swap(G, B);
        if (R < G) swap(R, G);
        if (G < B) swap(G, B);
        int ans = (long long)2 * ((long long)work(R - 1, G, B) + 2 * work(R, G, B) + work(R + 1, G, B)) % MOD;
        printf("%d
", ans);
    }
}