容斥 - 题解

标签与难度

标签: 动态规划, 状态压缩DP, 拉格朗日插值, 组合数学, 多项式

难度: 2500

题目大意喵~

主人，你好呀！这道题是这样的：我们有一个 $n \times m$ 的大棋盘，想在上面放上 $k$ 颗黑色的棋子，就像猫咪的肉球印章一样，噗にゅ~

但是有一个要求哦：任何两颗黑色棋子都不能放在相邻的格子里。这里的“相邻”是指上下左右四个方向。我们需要计算出有多少种不同的放置方法。因为答案可能会很大，所以要对 $10^9 + 7$ 取模。

两种放置方法被认为是不同的，只要有一个格子的颜色（黑色或白色）不一样就可以啦。

比如说，在一个 $2 \times 2$ 的棋盘上放 $2$ 个棋子，就有 2 种合法的方法，喵~

解题思路分析

这道题看起来像是一个组合计数问题，但是“不相邻”的限制让直接用组合公式变得非常困难，呜... 这时候，我们聪明的我就要拿出看家本领——动态规划（DP）啦！

小范围内的朴素DP：状态压缩DP

当棋盘的尺寸比较小的时候，我们可以用一种叫做“状态压缩DP”的技巧。我们可以一行一行或者一列一列地来填充棋盘。为了方便，我们总是让 $n$ 成为 $n$ 和 $m$ 中较小的那一个（如果不是，交换它们就好啦，结果是一样的嘛）。然后我们按列来DP。

我们定义一个状态 dp[j][mask][p] 表示：

当我们填充到第 j 列时，第 j 列的棋子摆放状态为 mask，并且整个棋盘的前 j 列总共已经摆放了 p 个棋子的方案数。

这里的 mask 是一个长度为 $n$ 的二进制数（也就是位掩码），如果第 i 位是 1，就代表第 j 列的第 i 行放了一颗棋子；如果是 0，就代表没放。

要从第 $j-1$ 列转移到第 $j$ 列，需要满足两个条件：

列内不相邻: mask 本身必须是合法的。也就是说，不能有任意两个 1 是相邻的。在二进制里，这就意味着 (mask & (mask << 1)) == 0。
列间不相邻: 第 $j$ 列的摆放 mask 不能和第 $j-1$ 列的摆放 prev_mask 在水平方向上相邻。这意味着 (mask & prev_mask) == 0。

所以，状态转移方程就是：

dp[j][\text{mask}][p] = \sum_{\substack{\text{prev\_mask is valid} \\ (\text{mask} \& \text{prev\_mask}) = 0}} dp[j-1][\text{prev\_mask}][p - \text{popcount}(\text{mask})]

其中 popcount(mask) 是 mask 中 1 的个数（也就是在第 j 列新放的棋子数）。

这个DP的时间复杂度大约是 $O(m \cdot k \cdot 4^n)$ ，因为每一列都有大约 $2^n$ 种状态，转移时又要枚举前一列的 $2^n$ 种状态。当 $n$ 很小（比如小于10）的时候，这是可以接受的。但是如果 $n$ 或者 $m$ 很大，这个方法就不行啦。

DP的优化：SOS DP (Sum over Subsets)

上面的转移可以优化！我们发现对于一个固定的 mask，它需要对所有满足 (prev_mask & mask) == 0 的 dp[j-1][prev_mask][...] 求和。这个条件等价于 prev_mask 是 ((1<<n) - 1) ^ mask（也就是 mask 的补集）的子集。

对所有子集求和？这正是 SOS DP 的拿手好戏！我们可以预处理一个 sos_dp 数组： sos_dp[super_mask][p] = sum_{sub is submask of super_mask} dp[j-1][sub][p]

这个预处理本身需要 $O(k \cdot n \cdot 2^n)$ 。之后，我们的转移就变成了：

dp[j][\text{mask}][p] = \text{sos\_dp}[\text{complement}(\text{mask})][p - \text{popcount}(\text{mask})]

这样总的DP复杂度就降到了 $O(m \cdot k \cdot n \cdot 2^n)$ ，能处理的 $n$ 的范围变大了一些，但还是不够呀！

喵的魔法：拉格朗日插值

当 $n$ 和 $m$ 非常大时，DP是肯定行不通的。我们需要一些更强大的魔法，喵~ 经过一番观察和（大量的）数学推导，可以发现一个惊人的性质：

对于固定的 $n$ 和 $k$ ，方案数 $f(m) = \text{Ans}(n, m, k)$ 是一个关于 $m$ 的、次数最高为 $k$ 的多项式！

为什么呢？我们可以直观地理解一下。在一个 $1 \times m$ 的行上放 $k$ 个不相邻的棋子，方案数是 $C(m-k+1, k)$ ，这是一个关于 $m$ 的 $k$ 次多项式。对于二维棋盘，情况更复杂，但最终的方案数仍然表现为多项式的性质。

知道了这个性质，事情就变得有趣了！如果我们想知道一个 $k$ 次多项式在某个点 $m$ 的取值，我们不需要知道它的系数。只要我们知道它在 $k+1$ 个不同点上的取值，就可以唯一确定这个多项式，并求出它在任何点的值。这就是拉格朗日插值法！

所以我们的策略是：

预计算: 用我们前面提到的状态压缩DP（可以用SOS优化），计算出当 $n$ 和 $m$ 都比较小的时候（比如 $n, m \le 2k$ ）的所有答案，存到一个表里。
插值求解:
- 情况一: 如果 $n$ 很小（比如 $n \le 2k$ ），但 $m$ 很大。我们就把 $n$ 固定，把方案数看成是关于 $m$ 的 $k$ 次多项式。我们从预计算的表里找出 $k+1$ 个点，比如 $(k, \text{Ans}(n,k,k)), (k+1, \text{Ans}(n,k+1,k)), \dots, (2k, \text{Ans}(n,2k,k))$ ，然后用拉格朗日插值法求出在 $m$ 处的函数值。
- 情况二: 如果 $n$ 和 $m$ 都很大。我们先固定 $m$ 为一个小值 $m'$ （比如 $m' \in [k, 2k]$ ），然后把方案数看成是关于 $n$ 的 $k$ 次多项式。用预计算的表和插值法求出 $\text{Ans}(n, m', k)$ 。我们对 $k+1$ 个不同的 $m'$ （比如 $m' = k, \dots, 2k$ ）都这样做一遍，就得到了 $k+1$ 个点 $(m', \text{Ans}(n, m', k))$ 。最后，再用这些点对 $m$ 进行一次插值，就得到最终的答案 $\text{Ans}(n, m, k)$ 啦！

这个“插值套插值”的方法，就像猫咪玩毛线球一样，一层一层解开，最后就能得到问题的核心答案！

代码实现

这是我根据上面的思路，精心编写的代码哦！里面包含了状态压缩DP（用于预计算）和拉格朗日插值法两部分，希望能帮助到你，喵~

cpp

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

using namespace std;

// 定义一个好用的 long long 类型别名
using ll = long long;

// 模数，要时刻记得取模哦
const int MOD = 1e9 + 7;

// 快速幂，用于计算模逆元
ll power(ll base, ll exp) {
    ll res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

// 模逆元
ll modInverse(ll n) {
    return power(n, MOD - 2);
}

// 拉格朗日插值函数
// points 是一系列 (x, y) 点
// x_val 是我们想要求值的横坐标
ll lagrange_interpolate(const vector<pair<ll, ll>>& points, ll x_val) {
    ll result = 0;
    int k = points.size();
    x_val %= MOD;

    for (int i = 0; i < k; ++i) {
        ll term = points[i].second;
        for (int j = 0; j < k; ++j) {
            if (i == j) continue;
            ll num = (x_val - points[j].first % MOD + MOD) % MOD;
            ll den = (points[i].first % MOD - points[j].first % MOD + MOD) % MOD;
            term = (term * num) % MOD;
            term = (term * modInverse(den)) % MOD;
        }
        result = (result + term) % MOD;
    }
    return result;
}

// K_MAX 是 k 的最大值
const int K_MAX = 10;
// N_DP_MAX 是我们用 DP 计算的较小维度的最大值
const int N_DP_MAX = 10; 
// M_DP_MAX 是我们用 DP 计算的较大维度的最大值
const int M_DP_MAX = 2 * K_MAX;

// 预计算的DP结果表 F[n][m][k]
int F[N_DP_MAX + 1][M_DP_MAX + 1][K_MAX + 1];
// 存储每个 n 对应的合法 mask 列表
vector<int> valid_masks[N_DP_MAX + 1];
// 存储每个 mask 的 popcount
int popcount_cache[1 << N_DP_MAX];

// 预计算所有小范围内的答案
void precompute() {
    // 缓存 popcount
    for (int i = 0; i < (1 << N_DP_MAX); ++i) {
        popcount_cache[i] = __builtin_popcount(i);
    }

    // 筛选出所有合法的 mask (列内不相邻)
    for (int n = 1; n <= N_DP_MAX; ++n) {
        for (int mask = 0; mask < (1 << n); ++mask) {
            if ((mask & (mask << 1)) == 0) {
                valid_masks[n].push_back(mask);
            }
        }
    }

    for (int n = 1; n <= N_DP_MAX; ++n) {
        // dp[j][mask_idx][k]
        vector<vector<vector<int>>> dp(M_DP_MAX + 1, vector<vector<int>>(valid_masks[n].size(), vector<int>(K_MAX + 1, 0)));
        
        // base case: 0列, 0棋子, 只有空mask一种方案
        dp[0][0][0] = 1; 

        for (int j = 1; j <= M_DP_MAX; ++j) { // 遍历列
            for (size_t mask_idx = 0; mask_idx < valid_masks[n].size(); ++mask_idx) {
                int mask = valid_masks[n][mask_idx];
                int pc = popcount_cache[mask];
                for (size_t prev_mask_idx = 0; prev_mask_idx < valid_masks[n].size(); ++prev_mask_idx) {
                    int prev_mask = valid_masks[n][prev_mask_idx];
                    if ((mask & prev_mask) == 0) { // 列间不相邻
                        for (int p = pc; p <= K_MAX; ++p) {
                            dp[j][mask_idx][p] = (dp[j][mask_idx][p] + dp[j - 1][prev_mask_idx][p - pc]) % MOD;
                        }
                    }
                }
            }
        }

        // 汇总结果到 F 表
        for (int m = 1; m <= M_DP_MAX; ++m) {
            for (int p = 0; p <= K_MAX; ++p) {
                ll total_ways = 0;
                for (size_t mask_idx = 0; mask_idx < valid_masks[n].size(); ++mask_idx) {
                    total_ways = (total_ways + dp[m][mask_idx][p]) % MOD;
                }
                F[n][m][p] = total_ways;
            }
        }
    }
}

// 解决问题的核心函数
ll solve(ll n, ll m, int k) {
    if (k == 0) return 1;
    if (n * m < k) return 0;
    if (n > m) swap(n, m);

    // Case 1: n 和 m 都在预计算范围内
    if (n <= N_DP_MAX && m <= M_DP_MAX) {
        return F[n][m][k];
    }

    // Case 2: n 在 DP 范围, m 超出范围 -> 对 m 插值
    if (n <= N_DP_MAX) {
        vector<pair<ll, ll>> points;
        for (int m_val = 1; m_val <= k + 1; ++m_val) {
            points.push_back({m_val, F[n][m_val][k]});
        }
        return lagrange_interpolate(points, m);
    }
    
    // Case 3: n 和 m 都超出范围 -> 双重插值
    vector<pair<ll, ll>> points_for_m;
    for (int m_val = 1; m_val <= k + 1; ++m_val) {
        vector<pair<ll, ll>> points_for_n;
        for (int n_val = 1; n_val <= k + 1; ++n_val) {
            points_for_n.push_back({n_val, F[n_val][m_val][k]});
        }
        ll y_val = lagrange_interpolate(points_for_n, n);
        points_for_m.push_back({m_val, y_val});
    }
    return lagrange_interpolate(points_for_m, m);
}

int main() {
    // 关闭同步，加速cin/cout
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // 预计算小数据
    precompute();

    ll n, m;
    int k;
    cin >> n >> m >> k;

    cout << solve(n, m, k) << endl;

    return 0;
}

复杂度分析

预计算时间复杂度: 我们的DP对每个 $n \in [1, N_{DP\_MAX}]$ 运行。对于固定的 $n$ ，DP的复杂度是 $O(M_{DP\_MAX} \cdot k \cdot |\text{valid\_masks}|^2)$ 。 $|\text{valid\_masks}|$ 的数量大致是斐波那契数级别的，远小于 $2^n$ 。这部分是一次性的，在程序开始时完成。对于本题的 $N_{DP\_MAX}=10$ , $M_{DP\_MAX}=20$ , $K_{MAX}=10$ ，这个计算量是完全可以接受的。
查询时间复杂度:
- 如果 $n,m$ 都在预计算范围内，是 $O(1)$ 。
- 如果需要单层插值，我们需要 $k+1$ 个点，拉格朗日插值本身的复杂度是 $O(k^2)$ 。
- 如果需要双重插值，我们需要为 $k+1$ 个不同的 $m'$ 分别计算插值，每次插值 $O(k^2)$ ，总共是 $O(k^3)$ 。最后再进行一次 $O(k^2)$ 的插值。总复杂度为 $O(k^3)$ 。因为 $k$ 非常小（最大为10），所以查询非常快！
空间复杂度:
- 预计算表 F 的大小是 $O(N_{DP\_MAX} \cdot M_{DP\_MAX} \cdot K_{MAX})$ 。
- DP过程中的 dp 数组大小是 $O(M_{DP\_MAX} \cdot |\text{valid\_masks}| \cdot K_{MAX})$ 。
- 总体空间是可控的。

知识点总结

这道题是多种强大算法的完美结合，就像一盘精致的猫饭，营养丰富，味道鲜美，喵~

状态压缩DP: 解决网格图、棋盘类问题且其中一维较小时的经典利器。通过位运算将一整行或一整列的状态压缩成一个整数，从而在状态中记录必要的信息。
SOS DP (Sum over Subsets): 一种用于优化状态转移的技巧。当转移需要对一个状态的所有子集/超集求和时，可以用它把 $O(4^n)$ 的暴力枚举优化到 $O(n \cdot 2^n)$ 。虽然我的最终代码为了清晰易懂没有用它，但这是优化这类DP的常用思路。
多项式性质: 许多组合计数问题的答案都可以表示为多项式。发现并利用这个性质是解决大规模计数问题的关键一步。
拉格朗日插值: 强大的数学工具，可以在知道一个 $d$ 次多项式上 $d+1$ 个点的值后，快速求出它在任意一点的值。它是从“计算小数据”到“解决大数据”的桥梁。

希望这篇题解能帮到你，如果还有问题，随时可以来找我玩哦，喵~！

容斥 - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

小范围内的朴素DP：状态压缩DP ​

DP的优化：SOS DP (Sum over Subsets) ​

喵的魔法：拉格朗日插值 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​