跳到主要内容

P11362 遗失的赋值

组合数学题，递推的优化思路很值得学习。

难度普及+/提高
算法组合数学、递推
日期2025-11-20

题意简述​

小 F 有一个数列 {x1,x2,…,xn}\{x_1,x_2,\ldots,x_n\}，其中 xi∈N∗x_i\in\mathbb{N}^* 且 xi≤vx_i\le v。现在小 F 为这个数列添加了 n−1n-1 条 AA 型限制和 mm 条 BB 型限制。

每条 AA 型限制 (ai,bi)(a_i,b_i) 的意思是：

  • 若 xi=aix_i=a_i，要求 xi+1=bix_{i+1}=b_i。
  • 若 xi≠aix_i\not=a_i，无限制。
  • ai,bi∈N∗a_i,b_i\in\mathbb{N}^* 且 ai,bi≤va_i,b_i\le v。

每条 BB 型限制 (ci,di)(c_i,d_i) 的意思是：

  • 要求 xci=dix_{c_i}=d_i。
  • ci,di∈N∗c_i,d_i\in\mathbb{N}^* 且 ci≤nc_i\le n，di≤vd_i\le v。

小 F 记住了所有 cjc_j 和 djd_j 的值，但把所有 aia_i 和 bib_i 的值都忘了。

现在小 F 想知道，有多少种 ai,bia_i, b_i 取值的组合，使得能够确保至少存在一个数列满足所有限制。方案数对 M=109+7M=10^9+7 取模。（不保证一定有解）

范围：1≤n≤109, 1≤m≤105, 2≤v≤109.1\le n\le 10^9,\space1\le m\le 10^5,\space2\le v\le 10^9.

思路​

一看这个 nn 这么大，不难想到解法应大约是 O(log⁡n)O(\log n) 左右的级别，而且很有可能是递推（因为 10910^9 存不下，没法保存 DP 状态）。

考虑一个区间 [1,k][1,k]，其中 1,k1,k 位置上都存在 BB 型限制（即端点的值被固定），而中间的位置没有。显然，此区间长度为 kk，区间内共有 k−1k-1 个 AA 型限制。设在区间内填充 AA 型限制（并有解）的总方案数为 f(k)f(k)，那么数列的所有项就以 BB 型限制的位置分成若干子区间，总方案数就是这些子区间的方案数之积。

现在我们考虑如何从 f(k−1)f(k-1) 推到 f(k)f(k)。

  • 如果令 a1=a_1= 左端点值，则 b1b_1 有 vv 种取法。每种取法下，又相当于固定了位置 22，求 [2,k][2,k] 的方案数，等价于求 [1,k−1][1,k-1] 的方案数。因而在这种情况下有 v×f(k−1)v\times f(k-1) 种方案。
  • 如果令 a1≠a_1\not= 左端点值（也就是限制不生效），则这些性质就与左端点“脱钩”了，随便填，一定有解。
    • 位置 11 上的限制，a1a_1 由于不能和左端点相同，故有 v(v−1)v(v-1) 种方案。
    • 其他 k−2k-2 个位置，a,ba,b 都随便选，故有 v2v^2 种方案。
    • 全部乘起来，有 v(v−1)×(v2)k−2=v2k−2−v2k−3v(v-1)\times(v^2)^{k-2}=v^{2k-2}-v^{2k-3}。
  • 边界情况：[1,2][1,2] 时，有 1+v(v−1)=v2−v+11+v(v-1)=v^2-v+1 种方案。

综上，有：

f(k)={v2−v+1k=2,vf(k−1)+v2k−2−v2k−3k>2.f(k)=\begin{cases} v^2-v+1 & k=2, \\ vf(k-1)+v^{2k-2}-v^{2k-3} & k>2.\\ \end{cases}

直接这样做，单个区间的时间复杂度为 O(nlog⁡n)O(n\log n)，总共 O(mnlog⁡n)O(mn\log n)，不能通过所有测试点。

数学 time​

试着展开：

f(k−1)=vf(k−2)+v2(k−1)−2−v2(k−1)−3=vf(k−2)+v2k−4−v2k−5.\begin{aligned} f(k-1)&=vf(k-2)+v^{2(k-1)-2}-v^{2(k-1)-3}\\ &=vf(k-2)+v^{2k-4}-v^{2k-5}. \end{aligned}

代入：

f(k)=v[vf(k−2)+v2k−4−v2k−5]+v2k−2−v2k−3=v2f(k−2)+v2k−3−v2k−4+v2k−2−v2k−3=v2f(k−2)−v2k−4+v2k−2.\begin{aligned} f(k)&=v[vf(k-2)+v^{2k-4}-v^{2k-5}]+v^{2k-2}-v^{2k-3}\\ &=v^2f(k-2)+v^{2k-3}-v^{2k-4}+v^{2k-2}-v^{2k-3}\\ &=v^2f(k-2)-v^{2k-4}+v^{2k-2}. \end{aligned}

再展开：

f(k−2)=vf(k−3)+v2(k−2)−2−v2(k−2)−3=vf(k−3)+v2k−6−v2k−7.\begin{aligned} f(k-2)&=vf(k-3)+v^{2(k-2)-2}-v^{2(k-2)-3}\\ &=vf(k-3)+v^{2k-6}-v^{2k-7}. \end{aligned}

再代入：

f(k)=v2[vf(k−3)+v2k−6−v2k−7]−v2k−4+v2k−2=v3f(k−3)+v2k−4−v2k−5−v2k−4+v2k−2=v3f(k−3)−v2k−5+v2k−2.\begin{aligned} f(k)&=v^2[vf(k-3)+v^{2k-6}-v^{2k-7}]-v^{2k-4}+v^{2k-2}\\ &=v^3f(k-3)+v^{2k-4}-v^{2k-5}-v^{2k-4}+v^{2k-2}\\ &=v^3f(k-3)-v^{2k-5}+v^{2k-2}. \end{aligned}

看出来了吗？让我们归纳一下：

f(k)=v1f(k−1)−v2k−3+v2k−2=v2f(k−2)−v2k−4+v2k−2=v3f(k−3)−v2k−5+v2k−2.⇒f(k)=vpf(k−p)−v2k−p−2+v2k−2.\begin{aligned} f(k)&=v^1f(k-1)-v^{2k-3}+v^{2k-2}\\ &=v^2f(k-2)-v^{2k-4}+v^{2k-2}\\ &=v^3f(k-3)-v^{2k-5}+v^{2k-2}.\\ \Rightarrow f(k)&=v^pf(k-p)-v^{2k-p-2}+v^{2k-2}. \end{aligned}

令 k−p=2k-p=2，即 p=k−2p=k-2，代入：

f(k)=vk−2f(2)−vk+v2k−2=vk−2(v2−v+1)−vk+v2k−2=vk−vk−1+vk−2−vk+v2k−2=v2k−2−vk−1+vk−2.\begin{aligned} f(k)&=v^{k-2}f(2)-v^k+v^{2k-2}\\ &=v^{k-2}(v^2-v+1)-v^k+v^{2k-2}\\ &=v^k-v^{k-1}+v^{k-2}-v^k+v^{2k-2}\\ &=v^{2k-2}-v^{k-1}+v^{k-2}. \end{aligned}

我们便可以用这个式子 + 快速幂在 O(mlog⁡n)O(m\log n) 的时间内求出答案。

边界情况​

当 c1>1c_1>1 时，会出现一个区间 [1,c1][1,c_1]（长度为 c1c_1，有 c1−1c_1-1 个 AA 型限制），其左端点无限制，右端点有限制。如何求这个区间的方案数？注意到每个位置上的限制其实可以随便取（和之前讨论的 a1≠a_1\not= 左端点类似），故总方案数就是 (v2)c1−1=v2c1−2(v^2)^{c_1-1}=v^{2c_1-2}。

类似地，当 cm<nc_m<n 时，会出现一个区间 [cm,n][c_m, n]（长度为 n−cm+1n-c_m+1，有 n−cmn-c_m 个 AA 型限制），方案数为 v2n−2cmv^{2n-2c_m}。

编码​

注意判断 BB 型限制有矛盾的时候方案数为 00、取模前要 +M+M。

用时 653 ms 内存 1.91 MB 
/*
* P11362 [NOIP2024] 遗失的赋值
*/
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull MOD = 1e9 + 7;
const ull MAXN = 1e9, MAXM = 1e5;
struct Rule {
    int c, d;
    bool operator<(const Rule& another) const {
        return c < another.c;
    }
} r[MAXM + 1];
ull qpow(ull a, ull b) {
    ull res = 1;
    while (b) {
        if (b & 1) res = (res * a) % MOD;
        a = (a * a) % MOD;
        b >>= 1;
    }
    return res;
}
ull T, n, m, v;
ull foo(ull k) {
    ull tot = 1;
    if (k > 2) {
        tot = (qpow(v, 2 * k - 2) + qpow(v, k - 2)) % MOD;
        tot = (tot - qpow(v, k - 1) + MOD) % MOD; // 取模前要 + MOD！！！
    } else if (k == 2) {
        tot = (v * v - v + 1) % MOD;
    }
    return tot;
}
int main() {
    cin >> T;
    while (T--) {
        cin >> n >> m >> v;
        for (int i = 1; i <= m; i++) cin >> r[i].c >> r[i].d;
        sort(r + 1, r + m + 1);
        ull k, ans = 1;
        if (r[1].c > 1) {
            ans = (ans * qpow(v, 2 * r[1].c - 2)) % MOD;
        }
        for (int i = 2; i <= m; i++) {
            k = r[i].c - r[i - 1].c + 1; // 区间长度
            if (r[i].c == r[i - 1].c && r[i].d != r[i - 1].d) {
                ans = 0;
                break;
            }
            ans = (ans * foo(k)) % MOD;
        }
        if (r[m].c < n) {
            ans = (ans * qpow(v, 2 * n - 2 * r[m].c)) % MOD;
        }
        cout << ans << '\n';
    }
    return 0;
}

参考​

本文思路受 题解：P11362 [NOIP2024] 遗失的赋值 启发。