P11362 [NOIP2024] 遗失的赋值解题报告

link

https://www.luogu.com.cn/problem/P11362

part1

n,m<=12,v<=2

暴力搜索即可，可能的二元限制不会太多

part2

m=1

注意到所有二元限制都满足要求

ans=(v*v)^{(n-1)}

part3

特殊性质A
每个位置都有数，不合法的情况只有

(c_i,d!=d_i)

part4

特殊性质B
~~没啥想法~~
相比于正解，这档分让你不用考虑一元限制之间的矛盾

part5

正解
先判断一元限制之间是否有矛盾
然后运用

part3

中正难则反的思想，对于相邻的两个一元限制，不合法的情况形如:

d1 v1,v1 v2,v2 v3,......,v(t-1) d!=d2

有

v^{t-1}*(v-1)

种
总共情况有

(v*v)^{2t}

种
把每一段乘起来，再用

part2

，把开头和结尾乘起来
然后就切掉了

AC code

CPP

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mod=1e9+7;
map<int,int> mp;
vector<int> a;
ll qpow(ll x,ll p){
	if(p==0) return 1;
	if(p%2==1) return x*qpow(x,p-1)%mod;
	ll t=qpow(x,p/2);
	return t*t%mod;
}
void solve(){
	mp.clear();
	a.clear();
	bool flag=false;
	int n,m;ll v;
	cin>>n>>m>>v;
	
	for(int i=1;i<=m;i++){
		int c,d;cin>>c>>d;
		if(mp[c]){
			if(d!=mp[c]){
				flag=true;
				break;
			}
		}
		else{
			mp[c]=d;
			a.push_back(c);
		}
	}
	if(flag){
		cout<<0<<endl;
		return;
	}
	sort(a.begin(),a.end());
	int sz=a.size();
	ll ans=1;
	for(int i=1;i<sz;i++){
		int t=a[i]-a[i-1];//二元限制个数 
		/*
		d1 v1
		v1 v2
		v2 v3
		...
		v(t-1) d!=d2
		v^(t-1)
		*/
		int tmp=qpow(v,t-1)*(v-1)%mod;//不合法 
		ans=(qpow(v,2*t)-tmp+mod)%mod*ans%mod;
	}	
	//开头
	if(a[0]>1) ans=qpow(v*v%mod,a[0]-1)*ans%mod;
	//结尾
	if(a[sz-1]<n) ans=qpow(v*v%mod,n-a[sz-1])*ans%mod;
	
	cout<<ans<<endl;
}
int main(){
	//freopen("in.in","r",stdin);
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int T;cin>>T;
	while(T--) solve();
	return 0;
}

P11362 [NOIP2024] 遗失的赋值解题报告

文章操作

link

part1

part2

part3

part4

part5

AC code

相关推荐

评论

P11362 [NOIP2024] 遗失的赋值解题报告