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

· · 题解

题目传送门。

思路

容易发现 a_i,b_i 仅和 x_{i-1},x_i 是否确定相关，令 dp_{i,0/1} 表示处理到第 i 位，是否确定 x_i 的取值，那么显然有转移：

当前遍历到 i，若存在 j 使得 c_j=i，也就是说这一位的取值已经被确定了，有转移：

dp_{i,1}=v^2dp_{i-1,0}+((v-1)v+1)dp_{i-1,1}

（当 x_{i-1} 不确定时，a_{i-1},b_{i-1} 显然能填任何数，当 x_{i-1} 确定时，若 a_{i-1}\not=x_{i-1}，有 v(v-1) 种方案，否则只有 1 种）

否则不存在 c_j=i，也就是说这一位填什么并不确定，那么有转移：

dp_{i,0}=v^2dp_{i-1,0}+v(v-1)dp_{i-1,1} dp_{i,1}=vdp_{i-1,1}

（和上面转移类似，不做解释）

直接做的时间复杂度为 \mathcal O (n)，可以用矩阵快速幂优化此过程，时间复杂度 \mathcal O (m\log n)。

（这式子应该是能直接算的，不过矩阵快速幂更好想点）

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int Mod=1e9+7;
const int Maxn=1e6+7;
int T;
int n,m,v;
ll f[Maxn][2];

struct Matrix{
    ll v[2][2];
    inline void clear(){memset(v,0,sizeof v);}
    inline void init(){v[0][0]=1,v[1][1]=1;}
    Matrix(){clear();}
};
inline Matrix operator*(const Matrix x,const Matrix y){
    Matrix z;
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            for(int k=0;k<2;k++)
                z.v[i][j]=(z.v[i][j]+x.v[i][k]*y.v[k][j]%Mod)%Mod;
    return z;
}
inline Matrix Ksmp(Matrix x,int b){
    Matrix z;z.init();
    while(b){
        if(b&1) z=z*x;
        x=x*x;
        b>>=1;
    }
    return z;
}

int main(){
    // freopen("assign2.in","r",stdin);
    // freopen("assign.out","w",stdout);
    scanf("%d",&T);
    while(T--){
        scanf("%d%d%d",&n,&m,&v);
        map<int,int>mp;
        bool tag=1;
        for(int i=1;i<=m;i++){
            int c,d;
            scanf("%d%d",&c,&d);
            if(mp[c] and mp[c]!=d) tag=0;
            mp[c]=d;
        }
        if(!tag){
            puts("0");
            continue;
        }
        Matrix ans,trs1,trs2;
        if(mp[1]) ans.v[0][1]=1;
        else ans.v[0][0]=1;
        trs1.v[0][0]=1ll*v*v%Mod,trs1.v[1][0]=1ll*v*(v-1)%Mod,trs1.v[1][1]=v;
        trs2.v[0][1]=1ll*v*v%Mod,trs2.v[1][1]=1ll*(v-1)*v%Mod+1;
        int lst=1;
        for(auto i:mp){
            int ps=i.first;
            if(ps==1) continue;
            ans=ans*Ksmp(trs1,ps-lst-1);
            ans=ans*trs2;
            lst=ps;
        }
        ans=ans*Ksmp(trs1,n-lst);
        printf("%lld\n",(ans.v[0][0]+ans.v[0][1])%Mod);
    }

    // system("pause");
    return 0;
}