这里写一个我在考场上差点想出来的、比较另类的做法。
若 \(\exists c_i=c_j(i\ne j),d_i\ne d_j\)，则答案显然为 \(0\)。
否则，我们可以将序列 \(x\) 中的数分为已确定和未确定两类。
设 \(f_0(i)\) 为当 \(x_i\) 未确定时前 \(i-1\) 个二元限制的方案数，\(f_1(i)\) 为当 \(x_i\) 确定时前 \(i-1\) 个二元限制的方案数。
所以对于 \(i\not\in c,i>1\)，有：
\[\begin{cases} f_0(i)=v^2\cdot f_0(i-1)+(v-1)v\cdot f_1(i-1)\\ f_1(i)=f_1(i-1)\\ \end{cases}\]而对于 \(i\in c,i>1\) ，有：
\[\begin{cases} f_0(i)=0\\ f_1(i)=v^2\cdot f_0(i-1)+[(v-1)v-1]\cdot f_1(i-1)\\ \end{cases}\]而对于 \(i=1\)，显然有 \(f_0=[i\not\in c],f_1=[i\in c]\)。
对于每个 \(i\in c\) 单独处理，再使用矩阵快速幂优化递推即可。
点击查看代码
// Problem: P11362 [NOIP2024] 遗失的赋值（民间数据）
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P11362
// Memory Limit: 512 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <algorithm>
#include <cstdio>
#include <map>
using namespace std;
typedef long long ll;
ll read() {
char c = getchar();
int v = 0, f = 1;
while (c < '0' || '9' < c) {
if (c == '-')
f = -1;
c = getchar();
}
while ('0' <= c && c <= '9') {
v = (v << 3) + (v << 1) + (c ^ 48);
c = getchar();
}
return v * f;
}
const ll mod = 1e9 + 7;
const ll M = 1e5 + 5;
ll T, n, m, v;
ll c[M], d[M];
map<ll, ll> mp;
ll s[M], cnt = 0;
struct Matrix {
ll a[2][2];
ll &operator()(ll x, ll y) { return a[x][y]; }
} f, g;
Matrix operator*(Matrix x, Matrix y) {
Matrix z;
z(0, 0) = z(0, 1) = z(1, 0) = z(1, 1) = 0;
for (ll i = 0; i < 2; i++)
for (ll j = 0; j < 2; j++)
for (ll k = 0; k < 2; k++)
z(i, j) = (z(i, j) + x(i, k) * y(k, j) % mod) % mod;
return z;
}
Matrix qpow(Matrix x, ll y) {
Matrix z;
z(0, 0) = z(1, 1) = 1;
z(0, 1) = z(1, 0) = 0;
while (y) {
if (y & 1)
z = z * x;
x = x * x;
y >>= 1;
}
return z;
}
void init() {
n = read(), m = read(), v = read();
g(0, 0) = v * v % mod, g(0, 1) = 0;
g(1, 0) = (v - 1) * v % mod, g(1, 1) = v;
mp.clear();
cnt = 0;
for (ll i = 1; i <= m; i++)
c[i] = read(), d[i] = read();
}
void update() {
f(0, 1) = (f(0, 0) * v % mod * v % mod +
f(0, 1) * ((v - 1) * v % mod + 1) % mod) %
mod;
f(0, 0) = 0;
}
void solve() {
for (ll i = 1; i <= m; i++) {
if (mp.count(c[i])) {
if (mp[c[i]] != d[i])
ok = false;
continue;
}
s[++cnt] = c[i];
mp[c[i]] = d[i];
}
sort(s + 1, s + cnt + 1);
f(1, 0) = f(1, 1) = 0;
if (s[1] == 1)
f(0, 0) = 0, f(0, 1) = 1;
else {
f(0, 0) = 1, f(0, 1) = 0;
f = f * qpow(g, s[1] - 2);
update();
}
for (ll i = 2; i <= cnt; i++) {
f = f * qpow(g, s[i] - s[i - 1] - 1);
update();
}
f = f * qpow(g, n - s[cnt]);
ll ans = (f(0, 0) + f(0, 1)) % mod;
printf("%lld\n", ans);
}
int main() {
T = read();
while (T--) {
init();
solve();
}
return 0;
}
可是洛谷上这个题的题解已经不让交了……
标签：Matrix,read,题解,ll,cdot,mod,NOIP2024,P11362 From： https://www.cnblogs.com/01bit/p/18585210