CF1237F Balanced Domino Placements

Solution

顯然可以先考慮橫著的骨牌，再考慮豎著的骨牌。但是思路卡在了選取橫著的骨牌會(huì)對(duì)豎著的骨牌的相鄰對(duì)數(shù)產(chǎn)生影響。

然而事實(shí)上我們只需要換一個(gè)統(tǒng)計(jì)順序，先考慮橫著的骨牌的列和豎著的骨牌的行，然后再考慮橫著的骨牌的行和豎著的骨牌的列（因?yàn)閱涡?列沒(méi)有雙行/列的必須相鄰的限制，因此可以簡(jiǎn)單地通過(guò)剩余行/列數(shù)統(tǒng)計(jì)）。

前面一項(xiàng)可以簡(jiǎn)單地$dp$得到，后面一項(xiàng)組合計(jì)數(shù)即可。

時(shí)間復(fù)雜度$O(n^2)$。

Code

#include <bits/stdc++.h>using namespace std;template<typename T> inline bool upmin(T &x, T y) { return y < x ? x = y, 1 : 0; } template<typename T> inline bool upmax(T &x, T y) { return x < y ? x = y, 1 : 0; }#define MP(A,B) make_pair(A,B) #define PB(A) push_back(A) #define SIZE(A) ((int)A.size()) #define LEN(A) ((int)A.length()) #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define fi first #define se secondtypedef long long ll; typedef unsigned long long ull; typedef long double lod; typedef pair<int, int> PR; typedef vector<int> VI; const lod eps = 1e-11; const lod pi = acos(-1); const int mods = 998244353; const int oo = 1 << 30; const ll loo = 1ll << 62; const int MAXN = 4005; const int INF = 0x3f3f3f3f;//1061109567 /*--------------------------------------------------------------------*/ inline int read() {int f = 1, x = 0; char c = getchar();while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }while (c >= '0' && c <= '9') { x = (x << 3) + (x << 1) + (c ^ 48); c = getchar(); }return x * f; } int tagx[MAXN], tagy[MAXN], fn[MAXN][MAXN], fm[MAXN][MAXN], fac[MAXN], inv[MAXN]; int upd(int x , int y) { return x + y >= mods ? x + y - mods : x + y; } int C(int x, int y) { return x < y ? 0 :1ll * fac[x] * inv[y] % mods * inv[x - y] % mods; } int quick_pow(int x, int y) {int ret = 1;for(; y ; y >>= 1) {if (y & 1) ret = 1ll * ret * x % mods;x = 1ll * x * x % mods;}return ret; } void Init(int n) {fac[0] = 1;for (int i = 1; i <= n ; ++ i) fac[i] = 1ll * fac[i - 1] * i % mods;inv[n] = quick_pow(fac[n], mods - 2);for (int i = n - 1; i >= 0 ; -- i) inv[i] = 1ll * inv[i + 1] * (i + 1) % mods; } signed main() {int n = read(), m = read(), k = read();Init(max(n, m));for (int i = 1; i <= k ; ++ i) tagx[read()] = 1, tagy[read()] = 1, tagx[read()] = 1, tagy[read()] = 1;fn[0][0] = 1;for (int i = 1; i <= n ; ++ i)for (int j = 0; j * 2 <= i; ++ j) fn[i][j] = (i > 1 && !tagx[i] && !tagx[i - 1]) ? upd(fn[i - 1][j], fn[i - 2][j - 1]) : fn[i - 1][j];fm[0][0] = 1;for (int i = 1; i <= m ; ++ i)for (int j = 0; j * 2 <= i; ++ j) fm[i][j] = (i > 1 && !tagy[i] && !tagy[i - 1]) ? upd(fm[i - 1][j], fm[i - 2][j - 1]) : fm[i - 1][j];int rn = 0, rm = 0;for (int i = 1; i <= n ; ++ i) rn += !tagx[i];for (int i = 1; i <= m ; ++ i) rm += !tagy[i];int ans = 0;for (int i = 0; i * 2 <= rn ; ++ i)for (int j = 0; j * 2 <= rm; ++ j) ans = upd(ans, 1ll * fac[i] * fac[j] % mods * C(rm - j * 2, i) % mods * C(rn - i * 2, j) % mods * fn[n][i] % mods * fm[m][j] % mods);printf("%d\n", ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的CF1237F Balanced Domino Placements(组合计数，dp)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。