Advertisement
Guest User

Untitled

a guest
Oct 16th, 2019
99
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.76 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. //{
  4. typedef long long ll;
  5. typedef pair<int,int> pii;
  6. typedef pair<ll,ll> pll;
  7. typedef pair<double,double> pdd;
  8. typedef long double ld;
  9. #define F first
  10. #define S second
  11. #define ALL(x) (x).begin(),(x).end()
  12. #define SZ(x) (ll)x.size()
  13. #define pb push_back
  14. #define eb emplace_back
  15. #define stp setprecision(30)<<fixed
  16. const int NF = 0x3f3f3f3f;
  17. const ll INF = 0x3f3f3f3f3f3f3f3f;
  18. const ll MO7 = 1e9 + 7;
  19. const ll MO9 = 1e9 + 9;
  20. const ll MO87 = 1e9 + 87;
  21. const ll MO93 = 1e9 + 93;
  22. const ll MO53 = 998244353;
  23. const ld PI = 3.14159265358979323846264338327950288;
  24. const ld eps = 1e-7;
  25. //}
  26. const ll MAX = 2e5 + 6, Mlg = __lg(MAX) + 2;
  27. ll C[3678][3678];
  28. ll fac[3678];
  29. void BB() {
  30. fac[0] = 1;
  31. for(int i = 1; i < 3678; ++ i) {
  32. fac[i] = fac[i - 1] * i % MO53;
  33. }
  34. for(int i = 0; i < 3678; ++ i)
  35. C[i][0] = 1;
  36. for(int i = 0; i < 3678; ++ i) {
  37. for(int j = 1; j <= i; ++ j) {
  38. C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MO53;
  39. }
  40. }
  41. return;
  42. }
  43. void build(int row[], ll arr[3610][3610], int h) {
  44. arr[0][0] = 1;
  45. arr[1][0] = 1;
  46. int nn = 0;
  47. for(int i = 1; i <= h; ++ i)
  48. if(!row[i])
  49. ++ nn;
  50. for(int i = 2; i <= h; ++ i) {
  51. for(int j = 0; j <= h; ++ j) {
  52. arr[i][j] = arr[i - 1][j];
  53. if(!row[i] && !row[i - 1]) {
  54. arr[i][j] = (arr[i][j] + arr[i - 2][j - 1]) % MO53;
  55. }
  56. }
  57. }
  58. ll dp[3678];
  59. memset(dp, 0, sizeof dp);
  60. for(int i = 0; i <= h; ++ i){
  61. dp[i] = arr[h][i];
  62. // debug(i, dp[i]);
  63. }
  64. for(int i = 0; i <= 3600; ++ i)
  65. for(int j = 0; j <= 3600; ++ j)
  66. arr[i][j] = 0;
  67. for(int i = 0; i <= h / 2; ++ i) {
  68. int lef = nn - (i + i);
  69. if(lef < 0) break;
  70. for(int j = 0; j <= lef; ++ j) {
  71. arr[i][j] = (arr[i][j] + dp[i] * C[lef][j] ) % MO53;
  72. // debug(i, j, arr[i][j]);
  73. }
  74. }
  75. return;
  76. }
  77. ll h, w, n;
  78. int row[3789], col[3789];
  79. ll arr[3610][3610];
  80. ll arc[3610][3610];
  81. int main() {
  82. ios_base::sync_with_stdio(0);cin.tie(0);
  83. cin >> h >> w >> n;
  84. BB();
  85. for(int i = 0; i < n; ++ i) {
  86. int r1, c1, r2, c2;
  87. cin >> r1 >> c1 >> r2 >> c2;
  88. row[r1] = 1;
  89. row[r2] = 1;
  90. col[c1] = 1;
  91. col[c2] = 1;
  92. }
  93. build(row, arr, h);
  94. build(col, arc, w);
  95. ll ans = 0;
  96. for(int i = 0; i <= 3600; ++ i) {
  97. for(int j = 0; j <= 3600; ++ j) {
  98. ans = (ans + arr[i][j] * arc[j][i] % MO53 * fac[i] % MO53 * fac[j]) % MO53;
  99. }
  100. }
  101. cout << ans << '\n';
  102. return 0;
  103. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement