题解：P11362 [NOIP2024] 遗失的赋值（民间数据）

随便做了做造了个民间数据。

考虑分段计算贡献后用乘法原理。先解决以下子问题：

$x_l,x_r$ 确定，求合法的 $(a_i,b_i),l\le i<r$ 数量。

反过来做，

(a_i,b_i)

不合法当且仅当：

\begin{cases} a_l=x_l;\\ a_{i+1}=b_i,&l\le i<r-1;\\ b_{r-1}\neq x_r. \end{cases}

对

l\le i<r-1

，

b_i

有

v

种可能取值；

b_{r-1}

有

v-1

种可能取值，共

v^{r-l-1}(v-1)

种。

又所有可能的

(a_i,b_i)

有

(v^2)^{r-l}

种，从而合法的

(a_i,b_i)

就有

f(l,r)=(v^{2(r-l)}-v^{r-l-1}(v-1))

种。

然后发现只有

x_k

值被限定时，

(a_i,b_i),1\le i<k

的

v^{2(k-1)}

种可能值和

(a_i,b_i),k\le i<n

的

v^{2(n-k)}

种可能值均合法。

从而设被限定了值的位置去重后为

k_1,\dots,k_{m'}

，则最终答案为

v^{2(k_1-1)}\cdot v^{2(n-k_m)}\prod\limits_{i=1}^{m'-1}f(k_i,k_{i+1})

。

注意需要判断是否有位置被赋了两个不同的值，用 map 维护即可做到时间复杂度

O(m(\log m+\log n))

，空间复杂度

O(m)

。

Code:

CPP

#define ll long long
const int mod=1e9+7;

inline ll qpw(ll x,int v=mod-2){
	ll res=1;while(v){
		if(v&1)res=res*x%mod;
		x=x*x%mod,v>>=1;
	}return res;
}

int n,m;
ll v,ans;
map<int,int>S;
map<int,int>::iterator ps,nx;
inline void solve(){
	cin>>n>>m>>v;
	S.clear();ans=1;
	for(int i=0,c,d;i<m;++i){
		cin>>c>>d;
		if(S.count(c)&&S[c]!=d)ans=0;
		else S[c]=d;
	}if(!ans){
		cout<<"0\n";
		return;
	}ps=nx=S.begin();
	ans=qpw(v,((*nx).first-1)*2);++nx;
	for(;nx!=S.end();++ps,++nx){
		int x=(*ps).first,y=(*nx).first;
		ans=ans*(qpw(v,(y-x)*2)-qpw(v,y-x-1)*(v-1)%mod+mod)%mod;
	}ans=ans*qpw(v,(n-(*ps).first)*2)%mod;
	cout<<ans<<"\n";
}

题解：P11362 [NOIP2024] 遗失的赋值（民间数据）

文章操作

相关推荐

评论

题解：P11362 [NOIP2024] 遗失的赋值（民间数据）