2019牛客暑期多校訓練營(第八場)Just Jump

題意： 終點位置為 L L L，中間點是 1 , 2 , ⋯   , L − 1 1,2,\cdots,L-1 1,2,⋯,L−1 ，開始位置在 0 0 0，每次必須走至少 d d d步,在第 t i t_i ti​步不能出現在 p i p_i pi​這個位置，問從 0 0 0到 L L L，有多少種走法。

**題解：**解法挺簡單的，先算出沒有 m m m個限制的情況下，求一個值，這個 f [ i ] = ∑ j = 0 i − d f [ i ] f[i] =\sum_{j=0}^{i-d}f[i] f[i]=∑j=0i−d​f[i]。然後容斥搞一下， m m m個限制，那麼問題來了，怎麼求剛好走 t i t_i ti​步到 p i p_i pi​。

這篇部落格的意義就在這了,先推薦個基神部落格。

這個求一個最後應該就等于 C ( p i − d ∗ t i + t i − 1 , t i − 1 ) C(p_i-d * t_i+t_i-1,t_i-1) C(pi​−d∗ti​+ti​−1,ti​−1)。

我們現在應該是對應這種情況

用插闆法，就是從 n + m n+m n+m個空隙裡面，選出 m − 1 m-1 m−1個位置出來，現在這就是多了個要求，相鄰兩個間隙不能小于 d d d

…,抽象了解下

你把這 m m m個 d d d全部推前面去，不久相當于直接在後面 n − m ∗ d − ( m − 1 ) n-m* d-(m-1) n−m∗d−(m−1)選 m − 1 m-1 m−1個

#include "bits/stdc++.h"

using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> P;
#define VNAME(value) (#value)
#define bug printf("*********\n");
#define debug(x) cout<<"["<<VNAME(x)<<" = "<<x<<"]"<<endl;
#define mid ((l + r) >> 1)
#define chl 2 * k + 1
#define chr 2 * k + 2
#define lson l, mid, chl
#define rson mid + 1, r, chr
#define eb(x) emplace_back(x)
#define pb(x) emplace_back(x)
#define mem(a, b) memset(a, b, sizeof(a));

const LL mod = (LL) 998244353;
const int maxn = (int) 1e7 + 5;
const LL INF = 0x7fffffff;
const LL inf = 0x3f3f3f3f;
const double eps = 1e-8;

#ifndef ONLINE_JUDGE
clock_t prostart = clock();
#endif

void f() {
#ifndef ONLINE_JUDGE
    freopen("../data.in", "r", stdin);
#endif
}

//typedef __int128 LLL;

template<typename T>
void read(T &w) {//讀入
    char c;
    while (!isdigit(c = getchar()));
    w = c & 15;
    while (isdigit(c = getchar()))
        w = w * 10 + (c & 15);
}

template<typename T>
void output(T x) {
    if (x < 0)
        putchar('-'), x = -x;
    int ss[55], sp = 0;
    do
        ss[++sp] = x % 10;
    while (x /= 10);
    while (sp)
        putchar(48 + ss[sp--]);
}

LL L, d, m;
P p[3005];

LL qz[maxn], l[maxn];

const int Comb_Maxn = 1e7 + 10;

LL Fac_inv[Comb_Maxn];
LL Fac[Comb_Maxn];

inline void Comb_init() {
    Fac_inv[0] = Fac[0] = 1;
    Fac_inv[1] = 1;
    for (int i = 1; i < Comb_Maxn; i++)
        Fac[i] = Fac[i - 1] * (LL) i % mod;
    for (int i = 2; i < Comb_Maxn; i++)
        Fac_inv[i] = (LL) (mod - mod / i) * Fac_inv[mod % i] % mod;
    for (int i = 1; i < Comb_Maxn; i++)
        Fac_inv[i] = (LL) Fac_inv[i - 1] * Fac_inv[i] % mod;
}

LL Comb(LL n, LL m) {
    if (n < 0 || m < 0)return 0;

    if (n < m)return 0;
    assert(n < Comb_Maxn && n >= m);
    assert(m < Comb_Maxn);

    return Fac[n] * Fac_inv[m] % mod * Fac_inv[n - m] % mod;
}

LL dp[maxn];

int main() {
    f();
    read(L);
    read(d);
    read(m);
    Comb_init();
    for (int i = 0; i < m; i++) {
        read(p[i].first);
        read(p[i].second);
    }
    sort(p, p + m);
    l[0] = 1;
    qz[0] = 1;
    for (int i = 1; i <= L; i++) {
        if (i >= d) {
            l[i] = qz[i - d];
        }
        qz[i] = (qz[i - 1] + l[i]) % mod;
    }
    for (int i = 0; i < m; i++) {
        dp[i] = Comb(p[i].second - d * p[i].first + p[i].first - 1, p[i].first - 1);
        if (dp[i] != 0) {
            for (int j = 0; j < i; j++) {
                dp[i] = (dp[i] -
                         Comb(p[i].second - p[j].second - d * (p[i].first - p[j].first) +
                              (p[i].first - p[j].first) - 1,
                              (p[i].first - p[j].first) - 1) * dp[j] % mod + mod) % mod;

            }
        }
    }
    LL ans = l[L];
    for (int i = 0; i < m; i++) {
        ans = (ans - dp[i] * l[L - p[i].second] % mod + mod) % mod;
    }
    printf("%lld\n", ans);

#ifndef ONLINE_JUDGE
    cout << "運作時間:" << 1.0 * (clock() - prostart) / CLOCKS_PER_SEC << endl;
#endif
    return 0;
}