记录编号	613644	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	4206.[HA CSP-X 2025]我要飞得更高	最终得分	100
用户昵称	2_16鸡扒拌面	是否通过	通过
代码语言	C++	运行时间	0.984 s
提交时间	2026-03-23 15:43:16	内存使用	4.95 MiB

#include<bits/stdc++.h>
#define M 998244353
#define N 100005
using namespace std;

int n,m;
vector<pair<int,int>> a,b;
long long f[N],p[N];

int main()
{
	freopen("rocket.in","r",stdin);
	freopen("rocket.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int l,r;
		cin>>l>>r;
		a.push_back({l,r});
	}
	sort(a.begin(),a.end());
	if(!a.empty())
	{
		int nl=a[0].first,nr=a[0].second;
		for(int i=1;i<m;i++)
		{
			if(a[i].first<=nr+1) nr=max(nr,a[i].second);
			else
			{
			    b.push_back({nl,nr});
			    nl=a[i].first;nr=a[i].second;
			}
		}
		b.push_back({nl,nr});
	}
	f[0]=1;p[0]=1;
	for(int i=1;i<=n;i++){
		long long t=0;
		for(auto&x:b){
			int l=x.first,r=x.second;
			int lo=i-r,hi=i-l;
			if(hi<0)continue;
			lo=max(0,lo);hi=min(i-1,hi);
			if(lo<=hi){
				if(lo==0)t=(t+p[hi])%M;
				else t=(t+p[hi]-p[lo-1]+M)%M;
			}
		}
		f[i]=t%M;
		p[i]=(p[i-1]+f[i])%M;
	}
	cout<<f[n]<<endl;
	return 0;
}