自动搬运

查看原文

来自洛谷，原作者为

	Raymondzll **

搬运于2025-08-24 22:48:51，当前版本为作者最后更新于2023-07-31 12:51:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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