P8894 求和题解

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