題意：你要從0跳到L矾瘾，每一步距離不能小于d女轿，并且下面有m組(t,p)代表一次攻擊，你不能在第t次調(diào)到位置p壕翩。求方案數(shù)蛉迹。()

題解：首先不考慮m次攻擊，可以用dp求出答案： 放妈。記錄一下前綴和就能在 的時(shí)間范圍內(nèi)求出答案北救，并且對(duì)于1~L之間的每個(gè)距離我們都能直接得到答案（方便計(jì)算答案）。

再考慮容斥減去不可行的方案芜抒。把攻擊排序珍策，這樣排在后面的攻擊一定不會(huì)影響排在前面的。 表示以第n個(gè)攻擊結(jié)尾宅倒，并且歷經(jīng)偶數(shù)次攻擊攘宙； 則對(duì)應(yīng)奇數(shù)次攻擊。

注意到對(duì)于從0走到某一次攻擊 ， 可以考慮用隔板法求出答案：

并且顯然地蹭劈，從第i個(gè)到第j的個(gè)數(shù)疗绣，就相當(dāng)于從0到

于是得到轉(zhuǎn)移方程，總復(fù)雜度

#include <algorithm>
#include <iostream>
#include <vector>
#define int int64_t
#define FOR(i, x, y) for (int i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (int i = (x), _##i = (y); i > _##i; --i)
using namespace std;
using pii = pair<int, int>;
const int mod = 998244353;
const int maxn = 1e7 + 10;
int l, d, m;

int bin(int x, int n, int MOD)
{
    int ret = MOD != 1;
    for (x %= MOD; n; n >>= 1, x = x * x % MOD)
        if (n & 1)
            ret = ret * x % MOD;
    return ret;
}

int invf[maxn], fac[maxn];
void fac_inv_init(int n, int p)
{
    fac[0] = 1;
    FOR(i, 1, n)
    fac[i] = i * fac[i - 1] % p;
    invf[n - 1] = bin(fac[n - 1], p - 2, p);
    FORD(i, n - 2, -1)
    invf[i] = invf[i + 1] * (i + 1) % p;
}

inline int C(int n, int m)
{ // n >= m >= 0
    return n < m || m < 0 ? 0 : fac[n] * invf[m] % mod * invf[n - m] % mod;
}

inline int F(int t, int p)
{
    if (p <= 0)
        return 0;
    return C(p - d * t + t - 1, t - 1);
}

int f[maxn], g[3005][2];
int32_t main()
{
    ios::sync_with_stdio(false);
    cin >> l >> d >> m;
    fac_inv_init(l + 1, mod);
    vector<pii> pos(m);
    for (auto &p : pos)
    {
        cin >> p.first >> p.second;
    }
    f[0] = 1;
    int s = 0;
    for (int i = 1; i <= l; i++)
    {
        if (i >= d)
            (s += f[i - d]) %= mod;
        f[i] = s;
    }
    sort(pos.begin(), pos.end());
    int ans = f[l];
    for (int i = 0; i < m; i++)
    {
        if (pos[i].second > l)
            continue;
        g[i][1] = F(pos[i].first, pos[i].second);
        for (int j = 0; j < i; j++)
        {
            int mem = F(pos[i].first - pos[j].first, pos[i].second - pos[j].second);
            for (int op = 0; op <= 1; op++)
            {
                g[i][op] = (g[i][op] + g[j][1 - op] * mem) % mod;
            }
        }
        ans = (ans - g[i][1] * f[l - pos[i].second] % mod + mod) % mod;
        ans = (ans + g[i][0] * f[l - pos[i].second] % mod) % mod;
    }
    cout << ans << endl;
}