Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- //{
- typedef long long ll;
- typedef pair<int,int> pii;
- typedef pair<ll,ll> pll;
- typedef pair<double,double> pdd;
- typedef long double ld;
- #define F first
- #define S second
- #define ALL(x) (x).begin(),(x).end()
- #define SZ(x) (ll)x.size()
- #define pb push_back
- #define eb emplace_back
- #define stp setprecision(30)<<fixed
- const int NF = 0x3f3f3f3f;
- const ll INF = 0x3f3f3f3f3f3f3f3f;
- const ll MO7 = 1e9 + 7;
- const ll MO9 = 1e9 + 9;
- const ll MO87 = 1e9 + 87;
- const ll MO93 = 1e9 + 93;
- const ll MO53 = 998244353;
- const ld PI = 3.14159265358979323846264338327950288;
- const ld eps = 1e-7;
- //}
- const ll MAX = 2e5 + 6, Mlg = __lg(MAX) + 2;
- ll C[3678][3678];
- ll fac[3678];
- void BB() {
- fac[0] = 1;
- for(int i = 1; i < 3678; ++ i) {
- fac[i] = fac[i - 1] * i % MO53;
- }
- for(int i = 0; i < 3678; ++ i)
- C[i][0] = 1;
- for(int i = 0; i < 3678; ++ i) {
- for(int j = 1; j <= i; ++ j) {
- C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MO53;
- }
- }
- return;
- }
- void build(int row[], ll arr[3610][3610], int h) {
- arr[0][0] = 1;
- arr[1][0] = 1;
- int nn = 0;
- for(int i = 1; i <= h; ++ i)
- if(!row[i])
- ++ nn;
- for(int i = 2; i <= h; ++ i) {
- for(int j = 0; j <= h; ++ j) {
- arr[i][j] = arr[i - 1][j];
- if(!row[i] && !row[i - 1]) {
- arr[i][j] = (arr[i][j] + arr[i - 2][j - 1]) % MO53;
- }
- }
- }
- ll dp[3678];
- memset(dp, 0, sizeof dp);
- for(int i = 0; i <= h; ++ i){
- dp[i] = arr[h][i];
- // debug(i, dp[i]);
- }
- for(int i = 0; i <= 3600; ++ i)
- for(int j = 0; j <= 3600; ++ j)
- arr[i][j] = 0;
- for(int i = 0; i <= h / 2; ++ i) {
- int lef = nn - (i + i);
- if(lef < 0) break;
- for(int j = 0; j <= lef; ++ j) {
- arr[i][j] = (arr[i][j] + dp[i] * C[lef][j] ) % MO53;
- // debug(i, j, arr[i][j]);
- }
- }
- return;
- }
- ll h, w, n;
- int row[3789], col[3789];
- ll arr[3610][3610];
- ll arc[3610][3610];
- int main() {
- ios_base::sync_with_stdio(0);cin.tie(0);
- cin >> h >> w >> n;
- BB();
- for(int i = 0; i < n; ++ i) {
- int r1, c1, r2, c2;
- cin >> r1 >> c1 >> r2 >> c2;
- row[r1] = 1;
- row[r2] = 1;
- col[c1] = 1;
- col[c2] = 1;
- }
- build(row, arr, h);
- build(col, arc, w);
- ll ans = 0;
- for(int i = 0; i <= 3600; ++ i) {
- for(int j = 0; j <= 3600; ++ j) {
- ans = (ans + arr[i][j] * arc[j][i] % MO53 * fac[i] % MO53 * fac[j]) % MO53;
- }
- }
- cout << ans << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement