P8894 「UOI-R1」求和 题解
Zi_Gao
·
·
题解
既然正面想不通，就从反面想，首先这个式子一串求和就是在干一个事情，每个区间选一个元素，把每种组合跑一遍，然后求出选出的元素中最大的一个，累加到答案中。那么，什么时候 $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 码风很丑，各位见谅。
```cpp
#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;
}
```