NOIP2024 T2 遗失的赋值题解

题目链接.

首先把所有的一元限制按照$c_j$从小到大排序. 后面我们直接假定$c_1, c_2, …, c_m$单调不减. 如果有两个$c_j$相等而对应的$d_j$不相等, 那一定是无解 (对应样例输入的第三组数据). 如果两个$c_j$相等而对应的$d_j$也相等, 则它们是一样的, 可以直接忽略掉其中一个.

然后你会发现只需要分别考虑每个区间上的情况. 具体来说, 我们可以先看任意两个相邻的$c_j$和$c_{j+1}$ (满足$c_j < c_{j+1}$). 在$[c_j, c_{j+1}]$这个区间上有$l = c_{j +1} - c_j$个二元限制可以考虑. 不考虑限制条件, 一共有$v^{2 l}$ 种可能的选法. 下面考虑哪些是不合法的. 不合法的应该是只能是有如下这个情形 (形成一个链):
$$
\displaylines{
(x_{c_j} = d_j) \rightarrow (x_{c_j + 1} = a_{c_j + 1}) \\
(x_{c_j + 1} = a_{c_j + 1}) \rightarrow (x_{c_j + 2} = a_{c_j + 2}) \\
(x_{c_j + 2} = a_{c_j + 2}) \rightarrow (x_{c_j + 3} = a_{c_j + 3}) \\
… \\
(x_{c_{j+1} - 2} = a_{c_{j+1} - 2}) \rightarrow (x_{c_{j+1} - 1} = a_{c_{j+1} - 1}) \\
(x_{c_{j+1} - 1} = a_{c_{j+1} - 1}) \rightarrow (x_{c_{j+1}} = b_{c_{j+1} -1})
}
$$
并且满足$b_{c_{j+1} -1} \neq d_{j+1}$. 这样的话, 里面有$a_{c_j + 1}, …, a_{c_{j+1} - 1}$共计$l -1$个变量, 它们的每个都有$v$个可能的取值, 而另有$b_{c_{j+1} -1}$有$v-1$个取值, 所以不合法的方案数量是$v^{l - 1} (v - 1)$. 所以这个区间对答案的贡献是一个乘数 $(v^{2l} - v^{l-1} (v-1))$.

然后还要额外算一下$[1, c_1]$和$[c_m, n]$这两个区间对答案的贡献, 注意它们是没有不合法的情况的.

上面这一通东西我自己打得都晕, 因此我怀疑没有人能看懂. 所以我决定给一个简单的例子再说明一下.

比如说我们有两个相邻的一元限制条件$x_2 = 3$和$x_5 = 8$, 假设$v = 10$. 那么我们考虑以下$l =3$个二元限制:
$$
\displaylines{
(x_2 = a_2) \rightarrow (x_3 = b_2) \\
(x_3 = a_3) \rightarrow (x_4 = b_3) \\
(x_4 = a_4) \rightarrow (x_5 = b_4) \\
}
$$
其中$a_2, a_3, a_4, b_2, b_3, b_4 \in \{1, …, 10\}$. 那么显然, 如果什么都不管, 我们有$10^{2 \times 3}$种取值.

然后考虑什么情况下这些二元限制会导致非法. 那么要导致非法, 就是说我们的限制必须能够发挥作用. 首先如果$a_2$不是$3$, 那么第一条限制就没有了作用. 如果第一条限制没有了作用, 那么$x_3$就可以任取, 而我们总可以取$x_3 \neq a_3$ (注意: 稍后我们讨论$v = 1$的情况, 现在$v \ge 2$), 这样第二条限制也没有了作用. 不难发现, 这个链条里面只要有一个限制失去作用, 后面的限制就全部失去作用. 同理, 我们必须有$b_2 = a_3$ 以及 $b_3 = a_4$. 又因为我们希望不合法, 所以我们要求$b_4 \neq 8$. 这样的话, 我们能自由取的值就是$a_3, a_4 \in \{1, …, 10\}$ 以及$b_4 \in \{1, 2, …, 7, 9, 10 \}$. 这样的话, 非法的答案数就是$10^2 \times 9$.

上面的探讨里面其实依赖于$v\ge 2$, 因为我们希望在$x_3$能够任取的时候规避掉$x_3 = a_3$的限制条件, 而这依赖于至少有两个数可以取, 即存在在$1$到$v$之间的某个数不等于$a_3$. 这个论证在$v = 1$的时候是不行的. 但是你会发现在$v = 1$的时候, 永远只能有$1$个方案 (甚至不可能无解, 因为所有的$d_j$也只能是$1$). 可以特判, 但神奇的是我们最终得到的求解公式是可以覆盖$v = 1$的情况的, 所以也可以直接不管.

代码如下. 可以通过民间数据.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,from,to) for(int i=(int)(from);i<=(int)(to);++i)
#define rev(i,from,to) for(int i=(int)(from);i>=(int)(to);--i)
const ll MOD = 1e9 + 7;

ll n, m, v;
vector<pair<int, int>> constraints;

ll qp(ll base, int e) { // 快速幂
    ll res = 1;
    while (e) {
        if (e & 1) res = res * base % MOD;
        base = base * base % MOD;
        e >>= 1;
    }
    return res;
}


void solve() {
    cin >> n >> m >> v;
    constraints.clear();
    rep(i, 1, m) {
        ll c, d;
        cin >> c >> d;
        constraints.emplace_back(c, d);
    }

    sort(constraints.begin(), constraints.end());
    ll ans = 1;

    rep(i, 0, m - 2) {
        auto [c1, d1] = constraints[i];
        auto [c2, d2] = constraints[i + 1];
        if (c1 == c2) {
            if (d1 == d2) continue;
            else {
                cout << "0\n";
                return;
            }
        }

        int l = c2 - c1;
        // 区间内总方案数
        ll all = qp(v, 2 * l);
        // 区间内不可行的方案
        ll invalid = qp(v, l - 1) * (v - 1) % MOD;
        ll valid = (all - invalid) % MOD;
        ans = ans * valid % MOD;
    }

    // 特判开头和结尾
    int first_c = constraints[0].first;
    if (first_c != 1) {
        int l = first_c - 1;
        ll all = qp(v, 2 * l);
        ans = ans * all % MOD;
    }

    int last_c = constraints[constraints.size() - 1].first;
    if (last_c != n) {
        int l = n - last_c;
        ll all = qp(v, 2 * l);
        ans = ans * all % MOD;
    }

    cout << ((ans % MOD) + MOD) % MOD << "\n";
}


int main() {
    ll T;
    cin >> T;
    while (T--) {
        solve();
    }
}

NOIP2024 T2 遗失的赋值 题解

NOIP2024 T2 遗失的赋值题解