Atcoder abc179 D - Leaping Tak（前缀和维护DP）

题意

给定n和k个区间，每个区间都不想相交，在每一个位置（p）都可以从任意一个区间拿出一个属于这个区间的数（d）然后跳转到p+d位置，但是位置不能超过n。从1开始到达n有多少种方法。

需要利用前缀和进行优化。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <string>
#include <vector>
#include <stack>
#include <map>
#include <sstream>
#include <cstring>
#include <set>
#include <cctype>
#include <list>
#include <bitset>
#define IO                       \
    ios::sync_with_stdio(false); \
    // cin.tie(0);                  \
    // cout.tie(0);
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int maxn = 1e6 + 100;
const int maxm = 1e6 + 10;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const LL mod = 998244353;
// int dis[8][2] = {0, 1, 1, 0, 0, -1, -1, 0, 1, -1, 1, 1, -1, 1, -1, -1};
int L[15], R[15];
LL sum[maxn];
LL dp[maxn];
int main()
{
#ifdef ONLINE_JUDGE
#else
    freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
#endif
    IO;
    LL n, k;
    cin >> n >> k;

    for (int i = 1; i <= k; i++)
        cin >> L[i] >> R[i];

    dp[1] = 1;
    sum[1] = 1;

    for (int i = 2; i <= n; i++)
    {
        for (int j = 1; j <= k; j++)
        {
            int l = L[j], r = R[j];
            dp[i] = (dp[i] + sum[max(0, i - l)] - sum[max(0, i - r - 1)] + mod) % mod;
        }
        sum[i] = (sum[i - 1] + dp[i]) % mod;
    }
    cout << dp[n] % mod;
    return 0;
}