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

VinstaG173 · 2024-11-30 16:12:57 · 题解

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

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

反过来做，(a_i,b_i) 不合法当且仅当：

对 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:

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