题解：P11362 [NOIP2024] 遗失的赋值记录

Chu_yh

1270人浏览 · 2025-05-05 16:01:22

Chu_yh · 2025-05-05 16:01:22 发布

P11362 [NOIP2024] 遗失的赋值我太蒻了，膜拜大佬 @VinstaG173。

容斥 DP 做法（什么鬼？太强了！）

题意简述

$n$ 个变量 $x_1, x_2, \ldots, x_n$ ，取值范围为 $1$ 至 $v$ 。

添加 $n - 1$ 条二元限制，第 $i$ （ $\leq i \leq n - 1$ ）条：若 $x_i = a_i$ ，则 $x_{i + 1} = b_i$ （ $a_i,b_i \in [1,v]$ ）， $x_i \neq a_i$ 时无约束。

给定序列长度 $n$ 和其中 $m$ 个元素的值： $x_{c_i}=d_i(1\le i\le m)$ ，求 $a_i, b_i$ （ $\leq i \leq n - 1$ ）取值组合数，使至少有一种变量赋值方案满足所有限制，结果对 $10^9 + 7$ 取模。

对于所有的测试数据，保证： $\leq T \leq 10$ ， $\leq n \leq 10^9$ ， $\leq m \leq 10^5$ ， $\leq v \leq 10^9$ 。

解题思路

采用分段统计，以已知值为分界。

求解一段的方案数

如下表，已知 $x_l$ 和 $x_r$ 的值，统计 $l\sim r$ 区间内的方案数。

1	$l$	3	4	5	6	7	$r$	9
$\bigcirc$	$x_l$	$\bigcirc$	$\bigcirc$	$\bigcirc$	$\bigcirc$	$\bigcirc$	$x_r$	$\bigcirc$
$a_1$	$a_l$	$a_3$	$a_4$	$a_5$	$a_6$	$a_7$	$a_r$	$a_9$
$b_1$	$b_l$	$b_3$	$b_4$	$b_5$	$b_6$	$b_7$	$b_r$	$b_9$

发现很难统计合法方案数，于是我们统计不合法方案数，并用总方案数减去它。

设区间内可容纳 $x$ 对 $a, b$ ，合法方案数为 $f (x)$ 。

总方案数

因为 $a,b\in [1,v]$ ，所以一对 $a, b$ 的方案数为 $v^2$ ，总共 $x$ 对，总方案数为 $v^2)^x=v^{2x}$ 。

不合法方案数

可以发现，方案不合法当且仅当它满足以下条件时：
$\begin{cases}x_l=a_l\\b_i=a_{i+1}(l\le i<r-1)\\x_r\ne b_{r-1}\end{cases}$

条件 1 中，因为 $x_l$ 一定，所以只有 $1$ 种可能。
条件 2 中，每个 $a_{i+1},b_i(l\le i<r-1)$ 为一对。因为 $b_i=a_{i+1}$ ，所以每对的方案数为 $v$ ，共 $x - 1$ 对，有 $v^{x-1}$ 种可能。
条件 3 中， $x_r$ 一定，且 $b_{r-1}\in[1,v]$ ，那么有 $v - 1$ 种可能。

通过乘法原理可知，不合法的方案数为 $1\times v^{x-1} \times(v-1)=v^x-v^{x-1}$ 种。

合法方案数

用总方案数减不合法方案数可得合法方案数 $f(x)=v^{2x}-v^x+v^{x-1}$ ，其中 $x = r - l$ 。

首尾处理

因为首尾端没有开头或结尾，即没有 $x_l$ 或 $x_r$ ，所以首尾段不存在不合法情况，合法方案数为 $v^{2x}$ ，首段 $l = 1$ ，尾端 $r = n$ 。

完整代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+2,mod=1e9+7;
long long T,ans,n,m,v;
pair<long long,long long> a[N];
inline long long read(){
	register long long X=0; register char C=getchar();
	while(C<48||57<C) C=getchar();
	while(47<C&&C<58) X=(X<<3)+(X<<1)+(C^48),C=getchar();
	return X;
}

inline long long qp(long long B){
	long long Res=1,A=v;
	for(A%=mod;B;(A*=A)%=mod,B>>=1) if(B&1) (Res*=A)%=mod;
	return Res;
}

inline long long Main(){
	n=read(),m=read(),v=read();
	for(register int i=1;i<=m;i++) a[i].first=read(),a[i].second=read();
	sort(a+1,a+m+1);
	ans=qp((a[1].first-1)<<1)%mod;//首段
	for(register int i=1;i<m;i++){
		if(a[i].first==a[i+1].first){
			if(a[i].second!=a[i+1].second) return 0;
			else continue;
		}
		register int x=a[i+1].first-a[i].first;
		(ans*=(((qp(x<<1)+mod-qp(x))%mod+qp(x-1))%mod))%=mod;//核心
	}
	(ans*=qp((n-a[m].first)<<1))%=mod;//尾段
	return ans;
}

int main(){
	T=read();
	while(T--) printf("%lld\n",Main());
	return 0;
}