P11362 [NOIP2024] 遗失的赋值（民间数据）

#include <iostream>
#include <vector>
#include <unordered_map>
#define MOD 1000000007
using namespace std;

// 快速幂计算 x^y % MOD
long long quick_pow(long long x, long long y, long long mod) {
    long long res = 1;
    while (y > 0) {
        if (y & 1) res = res * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return res;
}

void solve() {
    int T;
    cin >> T;
    while (T--) {
        int n, m, v;
        cin >> n >> m >> v;
        
        // 一元限制
        unordered_map<int, int> fixed_values;
        bool conflict = false;
        for (int i = 0; i < m; i++) {
            int c, d;
            cin >> c >> d;
            if (fixed_values.count(c) && fixed_values[c] != d) {
                conflict = true; // 矛盾
            }
            fixed_values[c] = d;
        }

        if (conflict) {
            cout << 0 << endl;
            continue;
        }

        // 二元限制的可能性
        long long valid_pairs = 0;
        for (int a = 1; a <= v; a++) {
            for (int b = 1; b <= v; b++) {
                bool is_valid = true;
                for (auto [pos, value] : fixed_values) {
                    if ((pos == 1 && a != value) || (pos == n && b != value)) {
                        is_valid = false;
                        break;
                    }
                }
                if (is_valid) valid_pairs++;
            }
        }

        // 有效二元限制的组合数
        valid_pairs %= MOD;
        long long result = quick_pow(valid_pairs, n - 1, MOD);
        cout << result << endl;
    }
}

int main() {
    solve();
    return 0;
}