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

题意简述

n n n 个变量 x 1 , x 2 , … , x n x_1, x_2, \ldots, x_n x1​,x2​,…,xn​,取值范围为 1 1 1 至 v v v。

添加 n − 1 n - 1 n−1 条二元限制,第 i i i( 1 ≤ i ≤ n − 1 1 \leq i \leq n - 1 1≤i≤n−1)条:若 x i = a i x_i = a_i xi​=ai​,则 x i + 1 = b i x_{i + 1} = b_i xi+1​=bi​( a i , b i ∈ [ 1 , v ] a_i,b_i \in [1,v] ai​,bi​∈[1,v]), x i ≠ a i x_i \neq a_i xi​=ai​ 时无约束。

给定序列长度 n n n 和其中 m m m 个元素的值: x c i = d i ( 1 ≤ i ≤ m ) x_{c_i}=d_i(1\le i\le m) xci​​=di​(1≤i≤m),求 a i , b i a_i, b_i ai​,bi​( 1 ≤ i ≤ n − 1 1 \leq i \leq n - 1 1≤i≤n−1)取值组合数,使至少有一种变量赋值方案满足所有限制,结果对 1 0 9 + 7 10^9 + 7 109+7 取模 。

对于所有的测试数据,保证: 1 ≤ T ≤ 10 1 \leq T \leq 10 1≤T≤10, 1 ≤ n ≤ 1 0 9 1 \leq n \leq 10^9 1≤n≤109, 1 ≤ m ≤ 1 0 5 1 \leq m \leq 10^5 1≤m≤105, 2 ≤ v ≤ 1 0 9 2 \leq v \leq 10^9 2≤v≤109。

解题思路

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

求解一段的方案数

如下表,已知 x l x_l xl​ 和 x r x_r xr​ 的值,统计 l ∼ r l\sim r l∼r 区间内的方案数。

1 l l l34567 r r r9
◯ \bigcirc ◯ x l x_l xl​ ◯ \bigcirc ◯ ◯ \bigcirc ◯ ◯ \bigcirc ◯ ◯ \bigcirc ◯ ◯ \bigcirc ◯ x r x_r xr​ ◯ \bigcirc ◯
a 1 a_1 a1​ a l a_l al​ a 3 a_3 a3​ a 4 a_4 a4​ a 5 a_5 a5​ a 6 a_6 a6​ a 7 a_7 a7​ a r a_r ar​ a 9 a_9 a9​
b 1 b_1 b1​ b l b_l bl​ b 3 b_3 b3​ b 4 b_4 b4​ b 5 b_5 b5​ b 6 b_6 b6​ b 7 b_7 b7​ b r b_r br​ b 9 b_9 b9​

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

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

总方案数

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

不合法方案数

可以发现,方案不合法当且仅当它满足以下条件时:
{ x l = a l b i = a i + 1 ( l ≤ i < r − 1 ) x r ≠ b r − 1 \begin{cases}x_l=a_l\\b_i=a_{i+1}(l\le i<r-1)\\x_r\ne b_{r-1}\end{cases} ⎩ ⎨ ⎧​xl​=al​bi​=ai+1​(l≤i<r−1)xr​=br−1​​

  • 条件 1 中,因为 x l x_l xl​ 一定,所以只有 1 1 1 种可能。
  • 条件 2 中,每个 a i + 1 , b i ( l ≤ i < r − 1 ) a_{i+1},b_i(l\le i<r-1) ai+1​,bi​(l≤i<r−1) 为一对。因为 b i = a i + 1 b_i=a_{i+1} bi​=ai+1​,所以每对的方案数为 v v v,共 x − 1 x-1 x−1 对,有 v x − 1 v^{x-1} vx−1 种可能。
  • 条件 3 中, x r x_r xr​ 一定,且 b r − 1 ∈ [ 1 , v ] b_{r-1}\in[1,v] br−1​∈[1,v],那么有 v − 1 v-1 v−1 种可能。

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

合法方案数

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

首尾处理

因为首尾端没有开头或结尾,即没有 x l x_l xl​ 或 x r x_r xr​,所以首尾段不存在不合法情况,合法方案数为 v 2 x v^{2x} v2x,首段 l = 1 l=1 l=1,尾端 r = n r=n 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;
}
Logo

集算法之大成!助力oier实现梦想!

更多推荐