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

题意简述

个变量 ，取值范围为 至 。

添加 条二元限制，第 （）条：若 ，则 （）， 时无约束。

给定序列长度 和其中 个元素的值：，求 （）取值组合数，使至少有一种变量赋值方案满足所有限制，结果对 取模 。

对于所有的测试数据，保证：，，，。

解题思路

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

求解一段的方案数

如下表，已知 和 的值，统计 区间内的方案数。

1 3 4 5 6 7 9

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

设区间内可容纳 对 ，合法方案数为 。

总方案数

因为 ，所以一对 的方案数为 ，总共 对，总方案数为 。

不合法方案数

可以发现，方案不合法当且仅当它满足以下条件时：

  • 条件 1 中，因为 一定，所以只有 种可能。
  • 条件 2 中，每个 为一对。因为 ，所以每对的方案数为 ，共 对，有 种可能。
  • 条件 3 中， 一定，且 ，那么有 种可能。

通过乘法原理可知，不合法的方案数为 种。

合法方案数

用总方案数减不合法方案数可得合法方案数 ，其中 。

首尾处理

因为首尾端没有开头或结尾，即没有 或 ，所以首尾段不存在不合法情况，合法方案数为 ，首段 ，尾端 。

完整代码

#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;
}