P8894 「UOI-R1」求和 题解

$\sum\limits_{s_1={p_1}}^{q_1}\sum\limits_{s_2={p_2}}^{q_2}\sum\limits_{s_3={p_3}}^{q_3} \cdots\sum\limits_{s_n={p_n}}^{q_n}\max\limits_{i=1}^ns_i$ 首先拿到这个式子，结合数据范围，模拟肯定超时了。这种时候一般需要把题目抽象出来，搞懂这个东西在说什么。

既然正面想不通，就从反面想，首先这个式子一串求和就是在干一个事情，每个区间选一个元素，把每种组合跑一遍，然后求出选出的元素中最大的一个，累加到答案中。那么，什么时候 $s_i$ 才能对答案做出贡献？肯定是 $s_i$ 是所有选出元素最大的时候，看似废话的一句话，实际就做完了题。考虑枚举每一个 $s_i$ ，对于每个 $s_i$ ，计算有多少个方案使得 $s_i$ 为最大。根据乘法原理，可得，使得最大值小于等于 $s_i$ 的方案数量为 $\prod_{i=1}^ns_i-p_i$ 记为 $ansleq_i$ ，但是现在要求得出最大值为 $s_i$ 的方案树，怎么办？考虑将方案结果小于 $s_i$ 剔除，也就是 $ansleq_i-ansleq_{i-1}$ ，就求得了使得 $s_i$ 为最大的方案数。最后累加 $\left(ansleq_i-ansleq_{i-1}\right)\times i$ 即可。

AC code 码风很丑，各位见谅。

#include <cstdio>
#include <algorithm>
#define INPUT_DATA_TYPE long long
#define OUTPUT_DATA_TYPE long long

struct node{
    int l,r;
}arr[5010];

long long ansleq[5010];

INPUT_DATA_TYPE read();
void print(OUTPUT_DATA_TYPE x);

int main(){
    register int i,j,min=0,max=0;
    register long long temp,ans=0;
    int n=read();

    for(i=0;i<n;++i){
        arr[i].l=read();
        arr[i].r=read();
        min=std::max(min,arr[i].l);//精确控制上下界
        max=std::max(max,arr[i].r);
    }

    for(i=min;i<=max;++i){
        temp=1;
        for(j=0;j<n;++j)
            temp=temp*(std::min(i,arr[j].r)-arr[j].l+1)%998244353;
        ansleq[i]=temp;
    }

    for(i=min;i<=max;++i) ans=(ans+(((ansleq[i]-ansleq[i-1]))*i%998244353)+998244353)%998244353;//注意ansleq[i]-ansleq[i-1]可能为负数

    print(ans);

    return 0;
}

INPUT_DATA_TYPE read(){
    register INPUT_DATA_TYPE x=0;register char f=0,c=getchar();
    while(c<'0'||'9'<c)f=(c=='-'),c=getchar();//?=if,:=else
    while('0'<=c&&c<='9')x=(x<<3)+(x<<1)+(c&15),c=getchar();
    return f?-x:x;
}

void print(OUTPUT_DATA_TYPE x){
    register char s[20];
    register int i=0;
    if(x<0){
        x=-x;
        putchar('-');
    }
    if(x==0){
        putchar('0');
        return;
    }
    while(x){
        s[i++]=x%10;
        x/=10;
    }
    while(i){
        putchar(s[--i]+'0');
    }
    return;
}