自动搬运

查看原文

来自洛谷，原作者为

	ducati If opportunities do not knock, build a door.

搬运于2025-08-24 22:31:12，当前版本为作者最后更新于2021-03-28 19:45:15，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

Description

ducati 热爱定义一些奇奇妙妙的东西。

• 定义两个序列不同，当且仅当它们的长度不同，或者它们长度相同但存在至少一组对应位上的值不同。

• 定义序列 $A$ 的权值为 $A$ 中所有数的乘积。

• 定义序列间的可达如下：

  • 做恰好 $t$ 次操作，每次操作选择 $A$ 的一个子区间（注意，选定的子区间可以为空）并将子区间中的数加 $1$ ；若存在一种操作方案，使得操作结束后 $A$ 与 $B$ 完全相同 ，则称 $A$ 可达 $B$。

• 定义序列 $A$ 的优美值为所有 $A$ 可达的不同序列的权值和。

现在，ducati 拥有了一个长度为 $n$ 的序列 $a$。他会多次查询一段区间的优美值。

你能帮帮好奇的他吗？你只需要输出每个答案对 $10007$ 取模的值就行啦。

$1 \le n,q \le 10^5$

Solution

Subtask 1

爆搜即可。

期望得分 $10$ 分。

Subtask 2

不难发现，我们实际上就是要求出，所有满足对 $a[l \sim r]$ 进行不超过 $t$ 次操作可以达到的 $b$ 的权值和。注意，确定下了 $b$ 之后，从 $a$ 变为 $b$ 的最少操作次数就是 P1969。

考虑 $dp$ 。

令 $f_{i,j,k}$ 表示，目前考虑到第 $i$ 个数，$a_i$ 被加了 $j$ 次 $1$ ，且要想达到当前的 $b$ 至少需要操作 $k$ 次。

根据 P1969 的套路，不难得到状态转移式：

$$f_{i,j,k}=\sum_{p=0}^j f_{i-1,p,k-(j-p)}(a_i+j) + \sum_{p=j+1}^k f_{i-1,p,k} (a_i+j) $$

第一个 $\sum$ 表示 $j \ge p$ 的情况，此时总操作次数要添加 $j-p$ 次；第二个 $\sum$ 表示 $j<p$ 的情况，总操作次数不需增加。

边界: $f_{l-1,0,0}=1$

答案：$\sum_{x=0}^t \sum_{y=0}^t dp_{r,x,y}$

时间复杂度 $O(nt^3)$，期望得分 $30$ 分。

Subtask 3

为了方便叙述，我们将这个三维 $dp$ 通过映射变为一个等价的二维 $dp$ 。具体地说，$f_{i,j,k}$ 被映射到了 $g_{i,(j-1)t+k}$。

考虑使用矩阵乘法来完成这个转移。

我们先处理出序列中每个位置的转移矩阵并建立出一棵线段树，维护区间内的矩阵乘积。

每次询问的时候，我们在线段树上找到那 $\log n$ 个被划分出来的区间，并将这些矩阵给乘起来即可。

时间复杂度 $O(nt^6+q \log n \ t^6)$ 。

期望得分 $60$ 分。

Subtask 4

考虑优化。

在每次询问的时候，我们先定义一个向量，其 $1$ 至 $t$ 位均为 $0$，且第 $0$ 位为 $1$ 。 我们在线段树上找到那 $\log n$ 个被划分出来的区间，然后直接向量乘矩阵即可。

考虑到当 $t=3$ 时每个矩阵的边长都是 $10$ ，于是总时间复杂度为

$$O(10^3 n+10^2 \ q \log n)$$

期望得分 $100$ 分。

Summary

本题主要考察了选手的 $dp$ 设计能力与优化能力，同时也考察了小数据结构与一些经典的优化套路(如向量乘矩阵，单次矩阵乘法对取模次数的优化)。

值得一提的是，本题似乎还可以通过矩阵前缀和以及矩阵求逆来解出。它虽然时间复杂度更为优秀（少一个 $\log n）$，但是它常数较大，有可能会被卡掉。

Code

#include <bits/stdc++.h>
#define PA pair<int,int>
#define fi first
#define se second
#define MP make_pair
using namespace std;
const int maxl=100005,mod=10007;

int read(){
	int s=0,w=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-')  w=-w;ch=getchar();}
	while (ch>='0'&&ch<='9'){s=s*10+(ch^'0');ch=getchar();}
	return s*w;
}
int n,q,t,blo,now,ans,le,ri,tot;
int a[maxl],pos[11][11],lis[11];

struct Matrix{int a[11][11];}tmp[maxl];

struct Segment_tree{
	int lson,rson,prod;
	Matrix p;
}tree[maxl<<1];

Matrix operator * (const Matrix &x,const Matrix &y){
	Matrix z;
	for (int i=0;i<=blo;i++){
		for (int j=0;j<=blo;j++){
			z.a[i][j]=0;
			for (int k=0;k<=blo;k++)  z.a[i][j]+=x.a[i][k]*y.a[k][j];
			z.a[i][j]%=mod;
		}
	}
	return z;
}

void pushup(int rt){
	int l=tree[rt].lson,r=tree[rt].rson;
	tree[rt].p = tree[l].p * tree[r].p;
	tree[rt].prod = (tree[l].prod * tree[r].prod) % mod;
}

int build_tree(int l,int r,int rt){
	rt=++tot;
	if (l==r){
		tree[rt].prod=a[l];
		tree[rt].p=tmp[l];
		return rt;
	}
	int mid=(l+r)>>1;
	tree[rt].lson=build_tree(l,mid,0);
	tree[rt].rson=build_tree(mid+1,r,0);
	
	pushup(rt);
	
	return rt;
}

int query_prod(int nl,int nr,int l,int r,int rt){
	if (nl<=l&&r<=nr){
		return tree[rt].prod;
	}
	int mid=(l+r)>>1,res=1;
	if (nl<=mid)  res = query_prod(nl,nr,l,mid,tree[rt].lson);
	if (nr>mid)  res *= query_prod(nl,nr,mid+1,r,tree[rt].rson);
	
	return res%mod;
}

void query_seg(int nl,int nr,int l,int r,int rt){
	if (nl<=l && r<=nr){
		int tmp[10];
		for (int i=0;i<=blo;i++)  tmp[i]=0;
		for (int i=0;i<=blo;i++){
			for (int j=0;j<=blo;j++){
				tmp[j] += lis[i] * tree[rt].p.a[i][j];
			}
		}
		for (int i=0;i<=blo;i++)  lis[i] = tmp[i]%mod;
		return;
	}
	int mid=(l+r)>>1;
	if (nl<=mid)  query_seg(nl,nr,l,mid,tree[rt].lson);
	if (nr>mid)  query_seg(nl,nr,mid+1,r,tree[rt].rson);
}

signed main(){
	n=read(),q=read(),t=read();
	for (int i=1;i<=n;i++)  a[i]=read();
	
	if (t){
		blo=((t+1)*(t+2))/2;
		for (int i=0;i<=t;i++){
			for (int j=i;j<=t;j++){
				pos[i][j]=now;
				now++;
			}
		}
		for (int i=1;i<=n;i++){
			for (int j=0;j<=t;j++){
				int val=a[i]+j;
				for (int k=j;k<=t;k++){
					for (int p=0;p<=k;p++){
						if (p<j){
							if (k-j+p>=0)  tmp[i].a[pos[p][k-j+p]][pos[j][k]]=val;
						}
						else tmp[i].a[pos[p][k]][pos[j][k]]=val;
					}
				}
			}
		}
	}
	build_tree(1,n,1);
	while (q--){
		le=read(),ri=read();
		if (t==0){
			ans = query_prod(le,ri,1,n,1);
		} 
		else{
			memset(lis,0,sizeof(lis));
			lis[0]=1,ans=0;
			
			query_seg(le,ri,1,n,1);
			for (int i=0;i<=t;i++)  ans=(ans+lis[pos[i][t]])%mod;
		}
		printf("%d\n",ans);
	}
	return 0;
}