P11362 [NOIP2024] 遗失的赋值
2025-11-23
题目大意
题目传送门
给定 n 个变量,记作 x1 到 xn,每个变量可以取 1 至 v 中任意整数。
另外有 m 个形如 (cj,dj) 的一元限制,意思是 xcj=dj。
定义二元限制 (ai,bi) 表示若 xi=ai,则 xi+1=bi;若 xi=ai,则不做限制。
需要求出所有给变量赋值使其满足所有限制的二元限制的取值组合的方案数,答案对 109+7 取模。
Solution
首先考虑一元限制对结果的影响,会发现所有的一元限制把序列隔成了若干段,任意取一个 ci。
容易发现,此时可以将 [ci,ci+1−1] 视作一段,考虑统计其中的方案数,正难则反,考虑什么情况下不满足这个限制。
如果 xci=aci 且 xci+1=bci 依次类推,直到最后一个 xci+1=bci+1−1,这个情况就是不正确的,中间共 ci+1−ci 个数,除了最后一个只有 v−1 种取值,其他都有 v 种取值,不可行方案数就是 vci+1−ci−1×(v−1),可行方案数为 v2×(ci+1−ci)−vci+1−ci−1×(v−1),其中一对二元限制有 v2 种选择。
这样我们就顺利统计完了方案数,至于最开头和最后则是直接加上即可。
Code
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PLL;
const int M = 1e5+10;
const LL MOD = 1e9+7;
PLL g[M];
LL qpow(LL a , LL b) {
LL res = 1;
while(b) {
if(b & 1) res = res * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return res;
}
void slove() {
LL n; int m; LL v;
scanf("%lld%d%lld" , &n , &m , &v);
for(int i = 1 ; i <= m ; i ++) {
scanf("%lld%lld" , &g[i].x , &g[i].y);
}
sort(g+1 , g+m+1 , [](const PLL& a , const PLL& b) {
return a.x < b.x;
});
vector<LL> f;
for(int i = 1 ; i <= m ; i ++) {
if(g[i].x != g[i-1].x) {
f.push_back(g[i].x);
} else if(g[i].y != g[i-1].y) {
puts("0"); return;
}
}
LL res = qpow(v , (f[0]-1)*2);
for(int i = 1 ; i < (int)f.size() ; i ++) {
LL tmp = qpow(v , (f[i]-f[i-1])*2) % MOD;
tmp -= qpow(v , f[i]-f[i-1]-1)*(v-1)%MOD;
tmp = (tmp+MOD)%MOD;
res = (res*tmp) % MOD;
}
res = (res*qpow(v , (n-f.back())*2)%MOD)%MOD;
printf("%lld\n" , res);
return;
}
int main() {
int T; scanf("%d" , &T);
while(T --) slove();
return 0;
}后话
一点参考文献?
