NOIP2024 遗失的赋值
给定一堆一元限制，问有多少种二元限制的方案，使得至少存在一种对 \(x_{1 \sim n}\) 赋值方法满足所有限制。
观察数据发现如下性质：
1、一元限制的作用：对于 \(x_{c_j} = d_j\)，当 \(a_{c_j} = d_j\) 是，强制 \(x_{c_j + 1} = b_{c_{j}}\)。
2、当 \(m = 1\) 时，答案是 \(v^{2n - 2}\)。因为模拟后可以发现这个限制没有什么用。
3、当没有一元限制干扰时，尽量按 \(x_i \ne a_i\) 填，限制最宽松（即需要满足的二元限制最少）。
4、最后一个一元限制不做限制。两个一元限制隔得较远，相当于在传递限制。
现在我们来考虑 \(m = 2\) 的情况。
一开始我以为这个贡献与一元限制的距离无关，就直接用相邻的计算方法算了所有，即 \([(v - 1) \times v + 1] ^ {len}\)，\(len\) 就是两个一元限制的距离。结果后来发现，对答案分解质因数后，里面死活会有一些根本不会在我的式子里出现的系数，这说明要么是不受限制的贡献统计有问题，要么是受限制的贡献统计有问题。中途犹豫了很久以为是不受限制的部分出错了，最后终于拿下性子手搓了一个距离为 \(2\) 的样例，发现贡献长得非常丑陋:
解释一下，其实容易发现这个式子有明显的递归特性，当下一个点不是另一个一元限制时，当前点裂成两种情况：
情况一：使 \(a_i\) 摆脱上一个一元限制，则 \(a_i\) 有 \(v - 1\) 种填法，\(b_i\) 就可以随便填了，故贡献系数使 \((v - 1)v\)，那么下一个位置 \(a, b\) 都可以随便填，贡献是 \(v^2\)。
情况二：使 \(a_i\) 保持限制，则 \(a_i\) 有 \(1\) 种填法，\(b_i\) 有 \(v\) 种填法，然后情况继续分裂下去。直到最后一个保持限制的位置，只有 \(1\) 的贡献。（就是上述式子最后那个 \(1\)）。
那么距离更大的情况，就继续递归就可以了。
经过一番艰苦的化简，发现：
距离为 \(1\) 是 \(v^4 - v^2 + v^1\)。
距离为 \(2\) 是 \(v^6 - v^3 + v^2\)。
\(\vdots\)
距离为 \(i\) 是 \(v^{2(i + 1)} - v^{i + 1} + v^i\)。
于是问题就变得简单了，只需要分别处理每两个一元限制的贡献，最后乘起来即可。
时间复杂度 \(O(Tm \log n)\)。
#include<bits/stdc++.h>
#define F(i,l,r) for(int i(l); i <= (r); ++ i)
#define G(i,r,l) for(int i(r); i >= (l); -- i)
#define int ll
using namespace std;
using ll = long long;
const int mod = 1e9 + 7;
const int N = 2e5;
int cnt = 0;
int quickmod(int x, int y){int ret = 1;while(y){if(y & 1) ret = ret * x % mod;x = x * x % mod;y >>= 1;}return ret;
}
int n, m, v, T, tt;
int a[N];
map<int, int>mp;
namespace task{void Main(){assert(mp[0] == 0);cin >> n >> m >> v;int flag = 1;int tot = 0;int ret = 1;F(i, 1, m){int c, d;cin >> c >> d;if(mp[c] > 0){if(mp[c] != d) flag = 0;}else {mp[c] = d; ++ tot; }a[i] = c;}if(!flag){cout << "0\n";}else{int r = m;sort(a + 1, a + r + 1);r = unique(a + 1, a + r + 1) - a - 1;F(i, 2, r){int len = a[i] - a[i - 1] - 1;int tmp = (quickmod(v, 2 * len + 2) - quickmod(v, len + 1) + quickmod(v, len)) % mod;ret = ret * tmp % mod;}ret = ret * quickmod(v * v % mod, a[1] - 1) % mod;ret = ret * quickmod(v * v % mod, n - a[r]) % mod;cout << (ret + mod) % mod << '\n';}mp.clear();}
}
signed main(){
// freopen("assign.in", "r", stdin);
// freopen("assign.out", "w", stdout);ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin >> T; tt = T;while(T --) task::Main();return fflush(0), 0;
}