自动搬运

查看原文

来自洛谷，原作者为

	Chis725 原UID：306199998，一个初生，基厨子（基尼奇3+1一炮115W还是太有操作了），300粉COS基尼奇

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

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

以下是正文

思路

这道题明显是一道动态规划的题，我们可以枚举它最后 $s$ 数列中的最大值的种类和个数，最终将它的最大值乘上他的方案数再将所有的相加就可以了。但是状态转移方程是比较难的。我们先假设最大值为 $i$，我们设 $f_{i,j}$ 是前 $j$ 项最大值不超过 $i$ 的方案数，然后我们就可以得出下面的状态转移方程。

if(i>=a[i].q)f[i][j] = f[i][j-1] * ( a[j].q - a[j].p + 1 ) % mod;
else f[i][j] = f[i][j-1] * ( i - a[j].p + 1 ) % mod;

我们还可以再简化一下。

f[i][j] = f[i][j-1] * ( min(a[j].q,i) - a[j].p + 1 ) % mod;

然后我们可以利用容斥原理求出大值为 $i$ 的方案数为 $f_{i,n}-f_{i-1,n}$。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
const int N = 5001;
struct node {
	int p,q;
}a[N];
int n,minn=0,maxn=0,s,t,ans;
signed main() {
	scanf("%lld",&n);
	for(int i = 1 ; i <= n ; i++ ) {
		scanf("%lld %lld",&a[i].p,&a[i].q);
		minn=max(minn,a[i].p);//最大值的最小的可能
		maxn=max(maxn,a[i].q);//最大值的最大的可能
	}
	for(int i = minn ; i <= maxn ; i++){
		s = 1;
		t = 1;
		for(int j = 1 ; j <= n ; j++){
			s = s * ( min(a[j].q,i) - a[j].p + 1 ) % mod;//s为f[i][j]
			t = t * ( min(a[j].q,i - 1) - a[j].p + 1)%mod;//t为f[i-1][j]
		}
		ans = ans + ( (s - t + mod ) * i % mod);//防止s-t为负数
		ans%=mod;
	}
	printf("%lld",ans);
	return 0;
}