用一元固定点切分变量链，相邻固定点区间用总方案减唯一强制失败链计数。
OJ: luogu
题目 ID: P11362
难度:普及+/提高
标签:组合计数数学快速幂
日期: 2026-06-22 19:11
题意
有 n 个变量，每个变量可以取 1..v。相邻变量之间原本有 n-1 条二元限制：
如果 x_i = a_i，则要求 x_{i+1} = b_i现在所有 a_i,b_i 都忘了，只记得 m 条一元限制 x_c = d。要求统计有多少种 (a_i,b_i) 的取值，使得至少存在一种变量赋值同时满足所有限制。
思路
先看一个小数据暴力：枚举所有边上的 (a_i,b_i)，再枚举所有变量赋值，判断是否存在合法赋值。
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;
struct Constraint {
int pos;
int value;
};
int T, n, m, v;
Constraint cons[15];
int edge_a[15], edge_b[15];
long long ans;
bool check_assignment(int pos, int x[]) {
if (pos > n) {
for (int i = 1; i <= m; i++) {
if (x[cons[i].pos] != cons[i].value) {
return false;
}
}
for (int i = 1; i < n; i++) {
if (x[i] == edge_a[i] && x[i + 1] != edge_b[i]) {
return false;
}
}
return true;
}
for (int value = 1; value <= v; value++) {
x[pos] = value;
if (check_assignment(pos + 1, x)) {
return true;
}
}
return false;
}
void enumerate_edges(int id) {
if (id == n) {
int x[15];
if (check_assignment(1, x)) {
ans++;
}
return;
}
for (int a = 1; a <= v; a++) {
for (int b = 1; b <= v; b++) {
edge_a[id] = a;
edge_b[id] = b;
enumerate_edges(id + 1);
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> T;
while (T--) {
cin >> n >> m >> v;
for (int i = 1; i <= m; i++) {
cin >> cons[i].pos >> cons[i].value;
}
ans = 0;
enumerate_edges(1);
cout << ans << '\n';
}
return 0;
}暴力无法处理 n,v 到 10^9 的数据。
先处理一元限制。如果同一个位置被限制成两个不同的值，那么无论二元限制怎么选，都不可能存在变量赋值，答案为 0。
否则，把所有固定点按位置排序。一元固定点会把整条变量链切成若干段。
没有被两个固定点夹住的边是自由的。因为至少一侧没有终点固定要求，总可以选择变量值绕开触发条件，所以每条这样的边有 v^2 种 (a,b)。
真正需要计数的是两个相邻固定点之间的区间。设左端固定为 x_p=A，右端固定为 x_q=B，距离：
L = q - p这段有 L 条边，总参数方案数为：
v^(2L)什么时候这段不合法？只有一种结构：从 A 出发，每一步都被强制触发，形成唯一的一条值链，最后还没有走到 B。
前 L-1 条边可以任意决定下一步被强制成什么值，共：
v^(L-1)最后一条边强制出的值不能等于 B，有：
v - 1种。因此不合法方案数为：
v^(L-1)(v-1)所以这个区间的合法贡献是：
v^(2L) - v^(L-1)(v-1)把所有相邻固定点区间的贡献乘起来，再乘上自由边的 v^2 次幂，就是答案。
代码
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007LL;
const int MAXM = 100005;
struct Constraint {
long long pos;
long long value;
};
int T, m;
long long n, v;
Constraint cons[MAXM];
bool cmp_constraint(Constraint a, Constraint b) {
if (a.pos != b.pos) {
return a.pos < b.pos;
}
return a.value < b.value;
}
long long power_mod(long long a, long long b) {
long long res = 1;
a %= MOD;
while (b > 0) {
if (b & 1LL) {
res = res * a % MOD;
}
a = a * a % MOD;
b >>= 1LL;
}
return res;
}
long long interval_count(long long len) {
long long total = power_mod(v * v % MOD, len);
long long bad = power_mod(v, len - 1) * ((v - 1) % MOD) % MOD;
return (total - bad + MOD) % MOD;
}
void solve_one() {
cin >> n >> m >> v;
for (int i = 1; i <= m; i++) {
cin >> cons[i].pos >> cons[i].value;
}
sort(cons + 1, cons + m + 1, cmp_constraint);
vector<Constraint> fixed_point;
bool ok = true;
for (int i = 1; i <= m; i++) {
if (!fixed_point.empty() && fixed_point.back().pos == cons[i].pos) {
if (fixed_point.back().value != cons[i].value) {
ok = false;
}
} else {
fixed_point.push_back(cons[i]);
}
}
if (!ok) {
cout << 0 << '\n';
return;
}
long long all_edge = v * v % MOD;
long long free_edges = 0;
long long ans = 1;
if (fixed_point.empty()) {
free_edges = n - 1;
} else {
free_edges += fixed_point[0].pos - 1;
free_edges += n - fixed_point.back().pos;
for (int i = 0; i + 1 < (int)fixed_point.size(); i++) {
long long len = fixed_point[i + 1].pos - fixed_point[i].pos;
ans = ans * interval_count(len) % MOD;
}
}
ans = ans * power_mod(all_edge, free_edges) % MOD;
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> T;
while (T--) {
solve_one();
}
return 0;
}复杂度
排序一元限制复杂度为
空间复杂度为
总结
这题的关键是分清楚统计对象：不是变量赋值数量，而是遗失的二元限制参数数量。
一元限制把链切成段。自由段每条边随便选；两个固定点之间的段，用“总方案数减去唯一强制失败链”即可得到贡献。