[NOIP2024] 遗失的赋值

xiaobing · 2024-11-30 18:02:09 · 题解

不存在的情况是同一个位置有不同的权值。 根据变量是否已知，可以将两个已知的变量间分为一个块。

此处将 p 设为已知，x 设为未知，则分为 [1,2]，[3,5]，[6,8]。

1. [1,2] 的可行方案显然是 v^{2\times2}。
2. [3,5] 可行方案不好直接算，但是不可行的方案好算。只有当 a_3=x_3,~b_3=a_4,~b_4=a_5,~b_5\neq x_6 时是不可行的，而 b_3,~b_4 是 1 到 v 都可以选，b_5 不能选 x_6，所以不可行方案是 v^{3-1}\times(v-1)，那么可行的方案就是 v^{2\times3}-v^{3-1}\times(v-1)。
3. [6,8] 的可行方案显然也是 v^{3\times2}。

接下来将思路转化为代码就可以了。

//#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lll __int128
#define ull unsigned long long
#define ui unsigned int
#define veci vector<int>
#define vecb vector<bool>
#define vecl vector<long long>
#define vecn vector<node>
#define vece vector<edge>
#define quei queue<int>
#define quen queue<node>
const int N = 1e5 + 10, inf = 0x5FFFFFFF, mod = 1e9 + 7;
const ll INF = 0x7FFFFFFFFFFFFFF;
ll qpow(ll x, ll k) {
    ll res = 1;
    while (k) {
        if (k & 1)res *= x, res %= mod;
        x *= x; x %= mod; k >>= 1;
    }
    return res;
}
int n, m, v;
struct node {
    int loc, w;
};
node p[N];
bool cmp(node u, node v) {
    return u.loc < v.loc;
}
void solve() {
    cin >> n >> m >> v;
    for (int i = 1; i <= m; i++)
        cin >> p[i].loc >> p[i].w;
    sort(p + 1, p + m + 1, cmp);
    veci tmp;
    for (int i = 1; i <= m; i++) {
        if (p[i].loc != p[i - 1].loc)
            tmp.push_back(p[i].loc);
        else if (p[i].w != p[i - 1].w) {
            cout << 0;
            return;
        }
    }
    ll ans = qpow(v, (tmp[0] - 1) << 1);
    for (int i = 1; i < tmp.size(); i++) {
        ll t = qpow(v, (tmp[i] - tmp[i - 1]) << 1);
        t -= (qpow(v, tmp[i] - tmp[i - 1] - 1) * (v - 1)) % mod;
        t %= mod; ans *= t; ans %= mod;
    }
    ans *= qpow(v, (n - tmp[tmp.size() - 1]) << 1); ans %= mod;
    cout << (ans + mod) % mod;
}
int main() {
    //freopen("train.in", "r", stdin);
    //freopen("train.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int T; cin >> T;
    while (T--) {
        solve();
        cout << '\n';
    }
    return 0;
}