CF1237F Balanced Domino Placements 题解

感觉远古 和现在 难度差远了。

不妨先考虑没有限制的情况。

首先对于这种问题，可以考虑转化成一个序列上的问题。

其实就是，有长度为 的序列 和长度为 的序列 ，有两种匹配方式：

• 匹配 ，对应横放的骨牌。
• 匹配 ，对应竖放的骨牌。

此时可以考虑做一个容斥原理。但是实际上你发现并不是很好容斥。

继续考虑，不妨考虑如何生成一组匹配。可以先考虑进行一些 的匹配，然后对于每个 的匹配，可以选择一个朝着后方扩展一位作为匹配的 。

但这样有一些难点难以解决，

• 因为匹配的顺序可能是乱序的，我们难以找到一个合适的顺序进行 DP。
• 难以考虑“朝后方扩展”的贡献。因为这个部分必须要两个序列一起考虑，因为两侧只能有一方可以朝后面扩展。

对于难点 ，有一个简单的想法就是延迟决策。我们发现，顺序的选择和格子的选择是相互独立，不受影响的。我们可以把相邻两个匹配到同一个格子的情况打包在一起考虑。假设选择了 个 和 个 出来，那么最后的匹配方案就是 个，显然最后生成的答案都互不相同。

此时还有第二个问题，就是如何保证两侧只有一个 ？一个简单的方法是，在 DP 选择格子的过程中记录选了几个 几个 ，但是复杂度爆炸。

我们发现，实际上 的限制是相当松的。任意一个作为 匹配的格子，你松掉这个格子换另一个没有占用的格子匹配也是合法的。对于一个没有占用的格子，你也可以直接拿过来作为匹配。因此我们将这部分也延迟决策，只需要最后在剩下来的格子中为对面的 挑出来 即可。

对于 和 ，分别求出 和 表示两侧选择 个 的方案数。枚举两侧分别选择了几个 ，假设 选择了 个 ， 选择了 个 ，最终的答案就是 。

此时考虑限制。由于题目保证限制合法，因此实际上是禁掉两个序列中某些位置不能用做匹配的一部分。在 DP 中判断一下后面两个格子是否都是可用的状态，最后计算答案的时候剩下的格子个数减掉禁掉的格子个数即可。细节可以见代码。

▶

INFO

#include <algorithm>
#include <iostream>
#include <vector>

sing uint = unsigned int;
sing ll = long long;
sing ull = unsigned long long;

amespace maths {
emplate <ull mod, class int_type = ll, class uint_type = ull>
lass modular {
 private:
   uint_type x;
   void norm() { x -= mod * (x >= mod); }

 public:
   modular() : x(0) {}
   modular(int_type _x) {
       if (_x < 0) {
           x = _x % (int_type)mod + (int_type)mod;
       }
       else {
           x = _x % mod;
       }
       norm();
       return;
   }
   friend modular operator+(const modular &lhs, const modular &rhs) {
       modular ret;
       ret.x = lhs.x + rhs.x;
       ret.norm();
       return ret;
   }
   friend modular operator-(const modular &lhs, const modular &rhs) {
       modular ret;
       ret.x = lhs.x + mod - rhs.x;
       ret.norm();
       return ret;
   }
   friend modular operator*(const modular &lhs, const modular &rhs) {
       return modular(lhs.x * rhs.x);
   }
   modular operator-() const {
       modular ret;
       ret.x = mod - x;
       return ret;
   }
   modular operator-=(const modular &b) { return *this = *this - b; }
   modular operator+=(const modular &b) { return *this = *this + b; }
   modular operator*=(const modular &b) { return *this = *this * b; }
   bool operator==(const modular &b) const { return x == b.x; }
   uint_type val() const { return x; }
   friend std::istream &operator>>(std::istream &is, modular &rhs) {
       is >> rhs.x;
       rhs.x %= mod;
       return is;
   }
   friend std::ostream &operator<<(std::ostream &os, const modular &rhs) {
       os << rhs.val();
       return os;
   }
;

sing modint998244353 = modular<998244353>;
sing modint1000000007 = modular<1000000007>;
 // namespace maths

amespace maths {
emplate <class T>
 quick_pow(T a, ull b, T id = T()) {
   T ret = id;
   for (; b; b >>= 1, a = a * a) {
       if (b & 1) {
           ret = a * ret;
       }
   }
   return ret;


emplate <class T>
 quick_pow(T a, const std::string &s, T id = T()) {
   T ret = id;
   for (size_t i = 0; i < s.size(); i++, a = a * a) {
       if (s[i] == '1') {
           ret = a * ret;
       }
   }
   return ret;


 // namespace maths

amespace maths {
sing mll = maths::modint998244353;
onst uint mod = 998244353;

ll inv(mll x) { return maths::quick_pow<mll>(x, mod - 2, 1); }

ll factrial(uint n) {
   static std::vector<mll> fact{1};
   for (size_t i = fact.size(); i <= n; i++) {
       fact.push_back(fact.back() * i);
   }

   return fact[n];


ll factrial_inv(uint n) {
   static std::vector<mll> inv_fact{1};
   for (size_t i = inv_fact.size(); i <= n; i++) {
       inv_fact.push_back(inv(i) * inv_fact.back());
   }

   return inv_fact[n];


ll combine(int n, int m) {
   if (n < 0 || m > n) {
       return 0;
   }
   else {
       return factrial(n) * factrial_inv(m) * factrial_inv(n - m);
   }

 // namespace maths

amespace solve {
sing mll = maths::modint998244353;

td::vector<mll> calculate(uint len, const std::vector<bool> used) {
   std::vector<std::vector<mll>> dp(len + 1, std::vector<mll>(len + 1));

   /**
    * dp_{i, j} for i 个位置选了 k 个 2 出来。
    */

   dp[0][0] = 1;

   for (size_t i = 0; i < len; i++) {
       for (size_t j = 0; j <= len; j++) {
           dp[i + 1][j] += dp[i][j]; // place nothing
       }

       if (i + 1 < len && !used[i] && !used[i + 1]) {
           for (size_t j = 0; j < len; j++) {
               dp[i + 2][j + 1] += dp[i][j];
           }
       }
   }

   return dp.back();


oid solve() {
   uint n, m, x;
   std::cin >> n >> m >> x;

   std::vector<bool> used_c(n), used_r(m);

   for (size_t i = 0; i < x; i++) {
       uint a, b, c, d;
       std::cin >> a >> b >> c >> d;
       --a, --b, --c, --d;

       used_c[a] = true;
       used_c[c] = true;
       used_r[b] = true;
       used_r[d] = true;
   }

   auto ans_c = calculate(n, used_c), ans_r = calculate(m, used_r);

   uint cnt_c = std::count(used_c.begin(), used_c.end(), true),
        cnt_r = std::count(used_r.begin(), used_r.end(), true);

   mll ans = 0;
   for (size_t i = 0; i <= n; i++) {
       for (size_t j = 0; j <= m; j++) {
           if (i * 2 + cnt_c > n || j * 2 + cnt_r > m) {
               continue;
           }

           uint rest_c = n - cnt_c - i * 2, rest_r = m - cnt_r - j * 2;

           ans += ans_c[i] * ans_r[j] * maths::combine(rest_c, j) *
                  maths::combine(rest_r, i) * maths::factrial(i) *
                  maths::factrial(j);
       }
   }

   std::cout << ans << "\n";

 // namespace solve

nt main() {
   solve::solve();
   std::cout << std::flush;
   return 0;