自动搬运

查看原文

来自洛谷，原作者为

	Genius_Star 跟你爆了

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

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

以下是正文

---

思路：

感觉不错，中等蓝吧……

考虑对第 $i$ 个数有三种可能的状态 $-1/1/0$ 分别表示：不可能是严格前缀最大值；一定是严格前缀最大值；可能是前缀最大值。

那么我们需要对于一个限制 $(x,y)$，确定一些位置的状态。

因为该限制需要满足：

$$\max\limits_{i=x+1}^y a_i \le \max\limits_{i=1}^x a_i < a_y $$

则区间 $[x+1,y-1]$ 不可能是严格前缀最大值，状态为 $-1$；且单点 $y$ 一定是严格前缀最大值。

经过这样的判断，如果一个点既一定又不可能，那么就无解。

然后考虑动态规划算法，定义 $dp_{i,j}$ 表示考虑序列 $a$ 中前 $i$ 项，其前缀最大值为 $j$ 时的可能方案，则状态转移方程为：

$$dp_{i,j}=\begin{cases} dp_{i-1,j} \times j & op_i=-1\\ \sum\limits_{k=1}^{j-1} dp_{i-1,k} + dp_{i-1,j} \times j& op_i = 0 \\ \sum\limits_{k=1}^{j-1} dp_{i-1,k}& op_i = 1\end{cases} $$

很容易想到用前缀和优化，定义：

$$s_{i,j}=\sum_{k=1}^j dp_{i,k}$$

状态转移方程优化为：

$$dp_{i,j}=\begin{cases} dp_{i-1,j} \times j & op_i=-1\\ s_{i-1,j-1} + dp_{i-1,j} \times j& op_i = 0 \\ s_{i-1,j-1} & op_i = 1\end{cases} $$

时间复杂度为 $O(NC)$，至此，我们已经获得了 75pts 的好成绩。

但是因为 $N$ 实在是太大了，重复的状态段特别多，考虑缩段，将连续的一段 $0$ 和 $-1$ 缩为一个点，因为状态为 $1$ 的个数是 $O(q)$ 级别的，可以不用缩点，而且缩点之后的状态转移不好计算。

定义第 $i$ 段的长度为 $A_i$，状态为 $OP_i$，即若 $OP_i=1$，则 $A_i=1$；然后定义 $dp_{i,j}$ 表示前 $i$ 段的前缀最大值为 $j$ 的方案数，则状态转移方程为：

$$dp_{i,j}=\begin{cases} dp_{i-1,j} \times j^{A_i} & OP_i = -1 \\ f(A_i,j) \sum\limits_{k=1}^{j-1} dp_{i-1,k} + dp_{i-1,j} \times j^{A_i}& OP_i = 0 \\ \sum\limits_{k=1}^{j-1} dp_{i-1,k} & OP_i = 1\end{cases} $$

其中 $f(x,y)$ 表示 $x$ 个在 $[1,y]$ 范围内的数，出现至少一个 $y$ 的方案数，则相当于任意取的方案数减去不出现 $y$ 的方案数：

$$f(x,y)=y^x-(y-1)^x$$

这个也可以进行前缀和优化：

$$dp_{i,j}=\begin{cases} dp_{i-1,j} \times j^{A_i} & OP_i = -1 \\ f(A_i,j) \times s_{i-1,j-1} + dp_{i-1,j} \times j^{A_i}& OP_i = 0 \\ s_{i-1,j-1} & OP_i = 1\end{cases} $$

这样加上快速幂的计算，时间复杂度为 $O(QC \log n)$。

完整代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const ll Q=505,N=10100,mod=1e9+7; 
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)
	  write(x/10);
	putchar(x%10+'0');
}
struct St{
	ll l,r;
	bool operator<(const St&rhs)const{
		if(r==rhs.r)
		  return l<rhs.l;
		return r<rhs.r;
	}
}h[N];
ll n,q,c,cnt=0,l=1;
ll A[Q],op[Q];
ll dp[Q][N],s[Q][N];
ll qpow(ll a,ll b){
	ll ans=1;
	while(b){
		if(b&1ll)
	 	  ans=(ans*a)%mod;
		a=(a*a)%mod;
		b>>=1ll;
	}
	return ans;
}
int main(){
//	freopen("A.in","r",stdin);
//	freopen("A.out","w",stdout);
	n=read(),q=read(),c=read();
	for(int x,y,i=1;i<=q;i++){
		x=read(),y=read();
		h[i]={x+1,y};
	}
	sort(h+1,h+q+1);
	for (int i=1;i<=q;i++){
		if(h[i].r==h[i-1].r)
		  continue;
		if(l>h[i].l){
			puts("0");
			exit(0);
		}
		if(l<h[i].l){
			cnt++;
			A[cnt]=h[i].l-l;
			op[cnt]=0;
		}
		if(h[i].l<h[i].r){
			cnt++;
			A[cnt]=h[i].r-h[i].l;
			op[cnt]=-1;
		}
		cnt++;
		A[cnt]=1;
		op[cnt]=1;
		l=h[i].r+1;
	}
	if(h[q].r<n){
		cnt++;
		A[cnt]=n-h[q].r;
		op[cnt]=0;
	}
//	for(int i=1;i<=cnt;i++){
//		write(op[i]);
//		putchar(' ');
//	}
//	putchar('\n');
	dp[0][0]=1;
	for(int i=0;i<=c;i++)
	  s[0][i]=1;
	for(int i=1;i<=cnt;i++){
		for(int j=1;j<=c;j++){
			ll x=qpow(j,A[i]),y=qpow(j-1,A[i]);
			if(op[i]==-1)
			  dp[i][j]=(dp[i-1][j]*x)%mod;
			else if(!op[i])
			  dp[i][j]=(((x-y+mod)%mod*s[i-1][j-1])%mod+(dp[i-1][j]*x)%mod)%mod;
			else
			  dp[i][j]=s[i-1][j-1];
			s[i][j]=(s[i][j-1]+dp[i][j])%mod;
		}
	}
//	for(int i=1;i<=cnt;i++){
//		for(int j=1;j<=c;j++){
//			write(s[i][j]);
//			putchar(' ');
//		}
//		putchar('\n');
//	}
	write(s[cnt][c]);
	return 0;
}