专业帮人做网站号码,集团公司网站怎么做,北京搬家公司哪家服务最好,专业网站建设微信网站定制CF1237F Balanced Domino Placements
Solution
显然可以先考虑横着的骨牌#xff0c;再考虑竖着的骨牌。但是思路卡在了选取横着的骨牌会对竖着的骨牌的相邻对数产生影响。
然而事实上我们只需要换一个统计顺序#xff0c;先考虑横着的骨牌的列和竖着的骨牌的行#xff0…CF1237F Balanced Domino Placements
Solution
显然可以先考虑横着的骨牌再考虑竖着的骨牌。但是思路卡在了选取横着的骨牌会对竖着的骨牌的相邻对数产生影响。
然而事实上我们只需要换一个统计顺序先考虑横着的骨牌的列和竖着的骨牌的行然后再考虑横着的骨牌的行和竖着的骨牌的列因为单行/列没有双行/列的必须相邻的限制因此可以简单地通过剩余行/列数统计。
前面一项可以简单地dpdpdp得到后面一项组合计数即可。
时间复杂度O(n2)O(n^2)O(n2)。
Code
#include bits/stdc.husing namespace std;templatetypename T inline bool upmin(T x, T y) { return y x ? x y, 1 : 0; }
templatetypename 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 pairint, int PR;
typedef vectorint 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;
}
