P9490题解

· · 题解

P9490 ZHY 的矩阵

前言

一道 DP 好题。

很多人（包括出题人）都反映此题题面过于抽象。我自己在做题时把题面翻译了一下。此部分不是太重要，能读懂即可。

考虑将二维的 0,1 矩阵转化为一维，a_i\in[1,k] 表示原矩阵中这一列的 1 位于第 a_i 行。若 a_i=0 表示这一列没有 0。

则题目限制转化为：若 a_i=a_j\ (i\neq j)，则 a_k \ (k\in (i,j)) 不能全为 0。

题目条件转化为：规定 a_i=x 或 a_i\neq x，那么等于条件只能有一种，不等条件可以有多种。我们称有这两种条件的点为断点。

下面进入正题。

解题思路

由出题人题解我们基本可以看到有 n\leq2\times10^5 推到 n\leq2\times10^9 的一个过程，故在此略过部分分。

令 f_{i,j} 代表直至第 i 个断点（第 0 个为 0，最后一个断点补上 n），最后一个非零 a_i 为 j 的方案数。若之前全都是 0，则 j=0。

先不考虑断点等于某数或不等于某数的限制，从上一个断点逐位递推的过程是怎样的呢？

记 s_i 为 \sum\limits_{j=1}^kf_{i,j}。

\begin{array}{|c|c|c|}\\f_{i-1,0}&f_{i-1,0}&f_{i-1,0}\\f_{i-1,1}&f_{i-1,0}+s_{i-1}&3\times(f_{i-1,0}+s_{i-1})+f_{i-1,0}\\f_{i-1,2}&f_{i-1,0}+s_{i-1}&3\times(f_{i-1,0}+s_{i-1})+f_{i-1,0}\\f_{i-1,3}&f_{i-1,0}+s_{i-1}&3\times(f_{i-1,0}+s_{i-1})+f_{i-1,0}\end{array}

好。先解释一下怎么推出来的。如果这一列的数（a_i）我们定为 p，那从上一位末位非 p 的 dp 方案可以通过这个加 p 操作转移成这一位末位为 p 的方案。

如果上一位末位是 p 呢？那显然这一位不能加 p 了（否则不符合前言中的题目限制）。但我们可以加 0 啊！所谓加 0，就是在原矩阵中这一列为空，一个 1 都没有，表现在 a_i 中就是 a_i=0。那上一位末位是 p 就可以转移到这一位末位是 p。

我们发现了什么？这一位末位是 p 可以由上一位任何末位转移而来！因此上面的表格中，每一列的末位非 0 都等于左边一列所有数的和。末位为 0 的方案数一直没变，显然。不理解可评论或私信。

有了这些基础我们就以逐断点递推很近了，但我们先要解决一下式子的问题。参照上面的表格，表格第二列的值为 f_{i-1,0}+s_{i-1}，第三列若把 3 扩展为 k，则为 k\times(f_{i-1,0}+s_{i-1})+f_{i-1,0}，再后面呢？k(k(f_{i-1,0}+s_{i-1})+f_{i-1,0})+f_{i-1,0}=(k^2+k+1)f_{i-1,0}+k^2s_{i-1}。

通式为 \frac{k^d-1}{k-1}f_{i-1,0}+k^{d-1}s_{i-1}。记这东西叫 g(d,i-1)。

准备工作均已完成，设 d 为断点 i 和 i-1 在原矩阵上列数的差。那 f_{i,p} 是不是就是 g(d,i-1) 呢？当然不是。现在我们可以关注断点 i 是等于型还是不等型。

等于：

设规定了 a_i=p。那么上一位末位（注意是位不是断点）为 p 的方案是不能转移到这一位的。有人会问前面按位推的时候为什么可以？那是加 0。这里强制加 p 就不行了。

因此 f_{i,p}=g(d-1,i-1)\times(k-1)+f_{i-1,0}=k^{d-1}f_{i-1,0}+(k-1)k^{d-2}s_{i-1}。

对于 j\neq p，f_{i,j}=0。

不等于：

设规定了 a_i\neq p1,p2,...，若 j\neq p1,p2,... 则 f_{i,j}=g(d,i-1)。如果 j=p1,p2,...，f_{i,j} 只能从上一位末位为 p1 转移而来，则 f_{i,j}=g(d-1,i-1)。

到这里重点的转移已经结束了。如果 d=1 那么转移会特殊一点，直接看代码即可。

const ll P=1000000007;
ll n,k,x,X;
ll f[200010][110],sum[200010];
int a[200010],b[200010],c[200010];
int l[200010],flag[200010];
void init(){
    cin>>n>>k>>x;
    for(int i=1;i<=x;i++){
        cin>>a[i]>>b[i]>>c[i];
        l[i]=b[i];
    }
    sort(l+1,l+x+1);
    X=unique(l+1,l+x+1)-l-1;//离散化
    for(int i=1;i<=x;i++){
        b[i]=lower_bound(l+1,l+X+1,b[i])-l;
        if(c[i]==1){
            if(++flag[b[i]]>1){cout<<0;exit(0);}
            for(int j=0;j<=k;j++)if(j!=a[i])f[b[i]][j]=-1;
        }else f[b[i]][a[i]]=-1;
    }
}
ll ksm(ll a,ll b){
    ll res=1;
    while(b){if(b&1)(res*=a)%=P;(a*=a)%=P;b>>=1;}
    return res;
}
ll invk;
int main(){
    init();invk=ksm(k-1,P-2);
    f[0][0]=1;
    if(l[X]!=n)l[++X]=n;
    for(int i=1;i<=X;i++){
        int d=l[i]-l[i-1];
        if(flag[i]){
            f[i][0]=0;
            for(int j=1;j<=k;j++)
                if(f[i][j]==0){
                    if(d==1)f[i][j]=sum[i]=(f[i-1][0]+sum[i-1]-f[i-1][j])%P;
                    else f[i][j]=sum[i]=(ksm(k,d-1)*f[i-1][0]%P+(k-1)*ksm(k,d-2)%P*sum[i-1]%P)%P;
                }else{
                    f[i][j]=0;
                }
        }else{
            f[i][0]=f[i-1][0];
            for(int j=1;j<=k;j++)
                if(f[i][j]==0){
                    if(d==1)f[i][j]=(f[i-1][0]+sum[i-1])%P;
                    else f[i][j]=((ksm(k,d)-1)*invk%P*f[i-1][0]%P+ksm(k,d-1)*sum[i-1]%P)%P;
                    (sum[i]+=f[i][j])%=P;
                }else{
                    if(d==1)f[i][j]=f[i-1][j];
                    else f[i][j]=((ksm(k,d-1)-1)*invk%P*f[i-1][0]%P+ksm(k,d-2)*sum[i-1]%P)%P;
                    (sum[i]+=f[i][j])%=P;
                }
        }
    }
    cout<<(sum[X]+f[X][0]+P)%P;
    return 0;
}