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

tang2hao4zhe2 · 2025-01-07 19:09:13 · 个人记录

link

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

part1

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

part2

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

part3

特殊性质A
每个位置都有数，不合法的情况只有(c_i,d!=d_i)

part4

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

part5

正解
先判断一元限制之间是否有矛盾
然后运用part3中正难则反的思想，对于相邻的两个一元限制，不合法的情况形如:

有v^{t-1}*(v-1)种
总共情况有(v*v)^{2t}种
把每一段乘起来，再用part2，把开头和结尾乘起来
然后就切掉了

AC code

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