专栏文章

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

PPolarisx
P11362题解参与者 17已保存评论 17

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
17 条
当前快照
1 份
快照标识符
@miqxjiew
此快照首次捕获于
2025/12/04 12:22
3 个月前
此快照最后确认于
2025/12/04 12:22
3 个月前
查看原文
题目传送门。

思路

容易发现 ai,bia_i,b_i 仅和 xi−1,xix_{i-1},x_i 是否确定相关，令 dpi,0/1dp_{i,0/1} 表示处理到第 ii 位，是否确定 xix_i 的取值，那么显然有转移：
当前遍历到 ii，若存在 jj 使得 cj=ic_j=i，也就是说这一位的取值已经被确定了，有转移：
dpi,1=v2dpi−1,0+((v−1)v+1)dpi−1,1dp_{i,1}=v^2dp_{i-1,0}+((v-1)v+1)dp_{i-1,1}
（当 xi−1x_{i-1} 不确定时，ai−1,bi−1a_{i-1},b_{i-1} 显然能填任何数，当 xi−1x_{i-1} 确定时，若 ai−1≠xi−1a_{i-1}\not=x_{i-1}，有 v(v−1)v(v-1) 种方案，否则只有 11 种）
否则不存在 cj=ic_j=i，也就是说这一位填什么并不确定，那么有转移：
dpi,0=v2dpi−1,0+v(v−1)dpi−1,1dp_{i,0}=v^2dp_{i-1,0}+v(v-1)dp_{i-1,1}
dpi,1=vdpi−1,1dp_{i,1}=vdp_{i-1,1}
（和上面转移类似，不做解释）
直接做的时间复杂度为 O(n)\mathcal O (n)，可以用矩阵快速幂优化此过程，时间复杂度 O(mlog⁡n)\mathcal O (m\log n)。
（这式子应该是能直接算的，不过矩阵快速幂更好想点）
CPP
#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;
}

评论

共 17 条评论，欢迎与作者交流。

正在加载评论...