Solution

首先我們要有敏銳的直覺: 我們將每一列中不選哪種顏色看作是一個序列, 則我們發(fā)現這個序列要求相鄰兩位的顏色不同. 我們還發(fā)現, 一個這樣的序列對應兩種不同的合法的棋盤, 因此統計合法棋盤數的問題, 就轉化為了統計合法序列數.

我們不妨設\(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\)段.

則我們發(fā)現\(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_JUDGEfreopen("board.in", "r", stdin);freopen("board.out", "w", stdout);#endifpw[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\n", ans);} }

轉載于:https://www.cnblogs.com/ZeonfaiHo/p/7592092.html

總結

以上是生活随笔為你收集整理的NOI模拟题4 Problem C: 填格子(board)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。