2019牛客暑期多校训练营(第八场)Just Jump

发表于 | 更新于 | 分类于 ， | 阅读次数：
本文字数： 3.9k | 阅读时长 ≈ 4 分钟

2019牛客暑期多校训练营(第八场)Just Jump
题意： 终点位置为$L$，中间点是$1,2,\cdots,L-1$ ，开始位置在$0$，每次必须走至少$d$步,在第。$t_i$
步不能出现在 $p_i$ 这个位置，问从 $0$ 到 $L$ ，有多少种走法。
题解：解法挺简单的，先算出没有$m$个约束的情况下，求一个值，这个 $f[i] =\sum_{j=0}^{i-d}f[i]$ 。然后容斥搞一下，$m$个限制，那么问题来了，怎么求刚好走 $t_i$ 步到 $p_i$ 。
这篇博客的意义就在这了,先推荐个基神博客。
这个求一个最后应该就等于$C_{p_i-dt_i+t_i-1}^{t_i-1}$。
我们现在应该是对应这种情况
用插板法，就是从$n+m$个空隙里面，选出$m-1$个位置出来，现在这就是多了个要求，相邻两个间隙不能小于$d$
…,抽象理解下

你把这$m$个$d$全部推前面去，不久相当于直接在后面$n-m * d-(m-1)$选$m-1$个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#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;
}