P11362【NOIP2024】遗失的赋值(assign) 题解

0 前言

NOIP2024场外选手。具体可见前面文章“写在xx之后”。

但是我希望今年不要再是场外选手了，所以温习一道去年的T2。

整体是推柿子，感觉我在这方面非常不擅长，因此来写一篇题解。

由于自己推柿子的能力太弱了，于是拜读了题解区最高赞题解，顺着思路来记录一下。

MyGO的赋值！！！！！

1 题意

有一个长度为 $n$ 的正整数序列 $x$，$\forall 1\le i\le n,x_i\in[1,V]$。现在有 $m$ 个一元限制，给出 $c_i,d_i$，要求满足 $x_{c_i}=d_i$，其余位置可以随便填。你需要对于每个 $ 1\le i<n$ 确定一个 $a_i$ 和 $b_i$，要求满足 $\forall 1\le i<n$，若 $x_i=a_i$，那么必须满足 $x_{i+1}=b_i$。你需要求出有多少组 存在满足所有限制的序列 的 $a,b$ 限制方案，两组限制序列不同当且仅当存在至少一个 $i$ 使得 $a_i$ 不同或者 $b_i$ 方案。

2 思路

下面着重说一说这题上的思路。

看到题目第一眼，先转化成上述题意。其实好像没有转化。

考虑对于一个整体的限制方案，序列长度为 $n$，那么限制方案的长度就是 $n-1$，加上每个位置有 $a_i,b_i$，那么整体就有 $2n-2$ 个数可以填，那么不考虑可行性的情况下，所有的限制方案数就是 $v^{2n-2}$。那么最终的答案就是所有限制方案数减去不可行的方案数。

接着我们观察到样例，发现第一个样例的第三组答案是 0 。因此我们考虑什么时候答案是 0。

很显然是已有的一元限制（下文称赋值）中有冲突的。比如存在 $i,j$，使得存在 $c_i=c_j$ 而 $d_i\neq d_j$。

接着我们考虑二元限制（下文称条件）之间的冲突与条件和赋值之间的冲突。

很显然，条件之间不肯能存在冲突，因为 $2\le v$，所以在没有赋值的位置上，一定存在一组方案避开掉所有的 $a_i$。

那么我们顺着上面的考虑，不难发现假若在有赋值的位置上存在和条件冲突的地方，那么就可以构造出来一组错解，也就是不可行的方案。

形式化的说，如果满足以下条件，那么这组限制方案不可行：

• 存在 $i,j$，使得 $x_i,x_j$ 都确定值，$x_i=d_i,x_j=d_j$，并且 $a_i=d_i,a_{i+1}=b_i，a_{i+2}=b_{i+1}$，以此类推，最后使得 $a_{j-1}=b_{j-2},b_{j-1}\neq d_j$。

这样就确定了两个已确定值的位置中间所有未知位置的值。并且使得条件确定了下来，和已有的赋值产生了冲突，因而构造错解。

因而我们考虑所有的区间 $[l,r]$ 使得 $1\le l<r<n,x_l=d_l,x_r=d_r$，也就是区间的端点位置都已确定值，并且中间的全都没有确定值。假设此区间长度为 $x+1$，那么就存在 $x$ 个位置可以任意选 $a_i,b_i$。因此我们考虑按照上面的思路，从总的方案数减去不可行的方案数，如下分析：

• 存在 $x$ 个可以填的位置，总的方案数为 $v^{2x}$。
• 考虑什么时候不可行，当且仅当如上文条件时。那么容易发现 $a_i$ 由 $b_{i-1}$ 决定，并且 $a_l=d_l$，因此有 $x-1$ 个赋值方案可以选择，方案数为 $v^{x-1}$。而且需要满足 $a_{r-1}\neq d_r$，所以这个位置还有 $v-1$ 的方案数。乘上就是 $v^x-v^{x-1}$。
• 因此这样一个区间合法的方案数就是 $v^{2x}-(v^x-v^{x-1})=v^{2x}-v^x+v^{x-1}$。
• 最后我们发现我们实际上不关心两端端点的取值和位置，只关心区间长度，因此我们可以对于每个如下的区间都用快速幂算，复杂度 $O(\log n)$。

然后对于前缀区间和后缀区间：

• 前缀区间可以视为区间第一个位置没有赋值，也就是整个区间可以随便填。方案数 $v^{2x}$。
• 后缀区间可以视为区间最后一个位置没有赋值，也就是整个区间也可以随便填，方案数 $v^{2x}$。

最后算出来每个满足条件的区间的方案数，相乘即可得到最后答案，不要忘记取模 $10^9+7$。

3 代码

这种题就不需要代码了吧。

看懂了思路自己完全可以写出来。

但是放上丑陋的核心代码仅供参考。

int n,m,v;
struct node{
    int c,d;
    friend bool operator==(node x,node y){
        return x.c==y.c;
    }
}val[N];
void solve(){
    sort(val+1,val+1+m,[](node x,node y){
        return x.c<y.c;
    });
    for(int i=1;i<m;++i){
        if(val[i+1]==val[i]&&val[i+1].d!=val[i].d){
            printf("0\n");
            return;
        }
    }
    m=unique(val+1,val+1+m)-val-1;
    int ans=1;
    for(int i=1;i<m;++i){
        int x=val[i+1].c-val[i].c;
        ans=(ans*(ksm(v,2*x,mod)+mod-ksm(v,x,mod)+ksm(v,x-1,mod))%mod)%mod;
    }
    int x=val[1].c-1;
    if(x!=0)ans=(ans*(ksm(v,2*x,mod))%mod)%mod;
    x=n-val[m].c;
    if(x!=0)ans=(ans*(ksm(v,2*x,mod))%mod)%mod;
    printf("%lld\n",ans);
}
signed main(){
    int t=read();
    while(t--){
        n=read(),m=read(),v=read();
        for(int i=1;i<=m;++i){
            val[i]={read(),read()};
        }
        solve();
    }    
}

4 时间复杂度分析

$T$ 次询问，$m$ 个区间，每个区间计算方案数 $O(\log n)$ 的复杂度，因此总复杂度 $O(Tm\log n)$。

5 后记

再听多听，还要多听。

再练多练，还要多练。