自动搬运

查看原文

来自洛谷，原作者为

	cwfxlh 会赢的！

搬运于2025-08-24 22:16:29，当前版本为作者最后更新于2023-07-14 20:25:55，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

P6009

模拟赛考了这道题，但不知道为什么没做出来。

DP 式子的转移是很好列的，令 $dp_{i}$ 表示当前以值为 $i$ 的元素结尾的不降子序列个数，特别的，令 $dp_0$ 表示空序列个数，则令当前枚举到了第 $j$ 个元素，转移为 $dp_{A_j}+=\sum_{u=0}^{A_j}dp_u$。很容易发现这个东西可以写成矩阵的形式，于是问题就变成了一个区间矩阵乘积的问题。我们不妨用前缀积与逆前缀积来维护。但是我们发现，转移写成的矩阵逆是很好求的，不需要高消求逆（数学计算推一下即可，形式与原矩阵相似），于是直接暴力乘出一个前缀积和逆前缀积，询问的时候相乘即可。复杂度 $O((n+q)k^3)$。

但是这个复杂度是过不去的，我们发现，转移写出来的矩阵只有 $O(k)$ 个元素有值，于是预处理的矩乘就可以加速到 $O(nk^2)$。询问的时候，答案矩阵可以由 $base\times InvPre(L-1)\times Pre(R)$ 得到，其中 $base$ 是一个仅有一个元素为 1 的 $1\times (k+1)$ 的矩阵，于是乘上 $base$ 后，矩阵大小只有 $k+1$，暴力矩阵乘的复杂度会变为 $O(qk^2)$，可以通过此题。当然利用前缀和可以优化到 $O(qk)$。总复杂度 $O((n+q)k^2)$。

代码：

#include<bits/stdc++.h>
#define MOD 1000000007
#define ll long long
using namespace std;
struct Matrix{
	int h;
	int w;
	int v[23][23];
}InvPre[50003],Pre[50003],res,ans;
Matrix operator*(Matrix A,Matrix B){
	res.h=A.h;
	res.w=B.w;
	for(int i=1;i<=res.h;i++){
		for(int j=1;j<=res.w;j++){
			res.v[i][j]=0;
			for(int u=1;u<=A.w;u++)res.v[i][j]=(res.v[i][j]+((ll)(A.v[i][u])*(ll)(B.v[u][j])%MOD))%MOD;
		}
	}
	return res;
}
void print(Matrix A){
	for(int i=1;i<=A.h;i++){
		for(int j=1;j<=A.w;j++)printf("%d ",(A.v[i][j]+MOD)%MOD);
		printf("\n");
	}
	return;
}
int n,k,q,w[50003],op1,op2,sum;
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)scanf("%d",&w[i]);
	scanf("%d",&q);
	Pre[0].h=Pre[0].w=InvPre[0].h=InvPre[0].w=k+1;
	for(int i=1;i<=k+1;i++)Pre[0].v[i][i]=InvPre[0].v[i][i]=1;
	for(int i=1;i<=n;i++){
		Pre[i].h=Pre[i].w=InvPre[i].h=InvPre[i].w=k+1;
		Pre[i]=Pre[i-1];
		for(int u=1;u<=k+1;u++){
			for(int p=1;p<=w[i]+1;p++)Pre[i].v[u][w[i]+1]=(Pre[i].v[u][w[i]+1]+Pre[i-1].v[u][p])%MOD;
		}
		for(int j=1;j<=k+1;j++){
			for(int u=1;u<=k+1;u++){
				InvPre[i].v[j][u]=(InvPre[i-1].v[j][u]-(500000004ll*(ll)(InvPre[i-1].v[w[i]+1][u])*(ll)(j<=w[i]+1))%MOD)%MOD;
			}
		}
	}
	while(q--){
		scanf("%d%d",&op1,&op2);
		ans.h=1;
		ans.w=k+1;
		for(int i=1;i<=k+1;i++)ans.v[1][i]=(int)(i==1);
		ans=(ans*InvPre[op1-1]);
		ans=(ans*Pre[op2]);
		sum=0;
		for(int i=1;i<=k+1;i++)sum=(sum+ans.v[1][i])%MOD;
		sum+=MOD;
		sum%=MOD;
		printf("%d\n",sum);
	}
	return 0;
}