题意
给定 \(n\) 和 \(k\) 个区间，并且保证 $ k \le 10$ 且互不相交。可以进行任意次操作，每次可以选择一个整数 \(j\)，\(j\) 要满足在其中一个给定的区间上，从当前位置向右移动 \(j\) 的距离。求 \(1\) 到 \(n\) 的方案数。
思路
提供一种数据结构的做法。
依次枚举 \(1\) 到 \(n\) 的每个点，对于每个点，先查询其方案数（已知），然后枚举每个区间，确定从当前点出发能跳到的区间，对其进行修改，最后查询 \(n\) 的方案数即可。
在本题中，需要支持区间修改和单点查询，树状数组是最佳选择。因此实现就非常简单了。
代码如下：
#include <iostream>
#include <cstdio>
#define MOD 998244353
using namespace std;
int n,m,l[101],r[101],b[1000001],t,ll,rr;
int lowbit(int x)
{
return x & -x;
}
int qh(int x)
{
int ans = 0;
for( int i = x ; i >= 1 ;i -= lowbit(i) )
ans = ( ans + b[i] ) % MOD;
return ans;
}
void xg(int x,int y)
{
for( int i = x ; i <= n ;i += lowbit(i) )
b[i] = ( ( b[i] + y ) % MOD + MOD) % MOD;
return;
}
int main()
{
cin >> n >> m;
for( int i = 1 ; i <= m ; i++ )
cin >> l[i] >> r[i];
xg ( 1 , 1 );//初始值为1
xg ( 2 , -1 );
for(int i = 1;i <= n;i++)
{
t = qh(i);
// cout << qh(n) << ' ' << t << endl;
for( int j = 1 ; j <= m ; j++ )
{
ll = i + l[j];
rr = min ( i + r[j] , n );
if ( ll <= n )
{
xg ( ll , t );
xg ( rr + 1 , -t );
}
}
}
cout << qh(n);
return 0;
}