A22562. 我要飞得更高（rocket）
题目描述
我要飞得更高（rocket）
题目描述
你是一只毛毛虫，想要飞离地球前往空间站。空间站位于距离地球n千米的位置，在1∼n−1的每整数千米位置都有一个休息站。你最开始在地球上，距离地球0千米。为了飞到空间站，你准备了m种火箭，其中i 号火箭能够前进Li--Ri千米。为了顺利到达空间站，有如下的限制条件：
1、每种火箭可以重复使用，且没有使用顺序的限制。
2、每次前进后，如果无法到达空间站，你需要到达距离地球整数千米的位置的休息站，在休息站修整后重新使用某种火箭，直到到达空间站。
3、宇宙很大，一旦和地球的距离超出了n千米就会失联，迷失在宇宙中，因此要避免这种情况。出发前，你想算算顺利到达空间站有几种方案，因为方案数可能很多，你只需要输出方案数对998244353 取模的结果。前进次数不同或前进次数相同但是存在某一步前进距离不同，则认为两个方案不同。
输入格式
第一行两个空格隔开的正整数表示n和m。
接下来m行，第i+1行两个空格隔开的正整数Li,Ri 描述第i个火箭的能力。
输出格式
输出一行一个非负整数表示方案数对998244353取模的结果。
样例输入1：
3 2
1 3
2 2样例输出1：
4样例输入2：
5 1
3 4样例输出2：
0说明/提示
【样例1解释】
第一个火箭可以让你前进1、2或3千米，第二个火箭可以让你前进2千米。到达1千米位置的休息站的方案只有一个，就是从地球前进1千米。到达2千米位置的休息站的方案有两个，一个是前进2千米，一个是前进1千米再前进1千米。到达3 千米的空间站的方案有四个，分别是前进3、前进2再前进1、前进1前进2、前进1前进1再前进1。询问你到达3千米的空间站的方案数，所以输出4。
【样例2解释】
只有一种火箭，可以让你前进3或4千米。到达3千米和4千米位置的休息站的方案都是1。无论怎么前进都只能停在中间或者距离超出5千米，无法顺利到达空间站，因此到达空间站的方案为0。
【测试点约束】对于所有数据，1≤n≤10^5,1≤m≤200,1≤Li ≤Ri≤n。
参考答案
#include<bits/stdc++.h>
using namespace std;
int n, m, cnt;
const int MOD=998244353;
long long dp[100005];
long long pre[100005];
struct qwe{ //统计区间的结构体
int l,r;
}a[205],A[205]; //a统计原区间，A统计合并后的区间
bool cmp(qwe x,qwe y){ //方便合并的排序规则
if(x.l!=y.l){
return x.l<y.l;
}else{
return x.r<y.r;
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>a[i].l>>a[i].r;
}
//设置一个无效的区间，用来标记结尾，方便最后一个区间放入A
a[m+1]={100005,100005};
sort(a+1,a+m+1,cmp); //按左端点排序，方便我们区间的合并
int k=0; //统计合并后的区间数量
int L=a[1].l,R=a[1].r; //用L,R表示当前正在合并的区间范围
//注意这里要设置无效区间，保证最后一个正常区间的统计
for(int i=2;i<=m+1;i++){
if(a[i].l<=R){ //若第i个区间左端点落在L-R的范围内，则合并
R=max(a[i].r,R); //判断区间长度有没有拓展
}else{ //若不能合并，将合并好的区间(L,R)放入A中
A[++k].l=L;
A[k].r=R;
L=a[i].l; //开启新的区间合并
R=a[i].r;
}
}
//注意：这里如果不设置a[m+1],不容易处理最后一个区间放入A的过程，容易导致错误
dp[0]=1;
pre[0]=1; //前缀和数组
for(int i=1;i<=n;i++){
for(int j=1;j<=k;j++){
int left=i-A[j].r;
int right=i-A[j].l; //(left~right)范围内都可到达i位置
if(right<0){ //若右端点小于0，表示范围不存在，跳过
continue;
}
if(left<0){ //左端点小于0则从0开始
left=0;
}
if(left-1>=0) //经典前缀和求区间累加的方法，不再赘述
dp[i]=(dp[i]+pre[right]-pre[left-1]+MOD)%MOD;
else
dp[i]=(dp[i]+pre[right])%MOD; //right>=left-1>=0，我们只需计算0~right累加之和pre[right]
}
pre[i]=(pre[i-1]+dp[i]%MOD)%MOD; //更新前缀和数组
//求余时选择+MOD再求余，一个避免负数求余出错的好习惯
}
cout<<dp[n];
return 0;
}