2019牛客第八场J题 (Just Jump) 隔板法 + 容斥

题意：你要从0跳到L，每一步距离不能小于d，并且下面有m组(t,p)代表一次攻击，你不能在第t次调到位置p。求方案数。( $L \le 10^7, m \le 3000$ )

题解：首先不考虑m次攻击，可以用dp求出答案： $dp[i]=\sum_{j=1}^{i-d} dp[j]$ 。记录一下前缀和就能在 $O(L)$ 的时间范围内求出答案，并且对于1~L之间的每个距离我们都能直接得到答案（方便计算答案）。

再考虑容斥减去不可行的方案。把攻击排序，这样排在后面的攻击一定不会影响排在前面的。 $g[n][0]$ 表示以第n个攻击结尾，并且历经偶数次攻击； $g[n][1]$ 则对应奇数次攻击。

注意到对于从0走到某一次攻击 $(t_i,p_i)$ ，可以考虑用隔板法求出答案： ${p_i-td_i+t_i-1}\choose {t_i-1}$

并且显然地，从第i个到第j的个数，就相当于从0到 $(t_i-t_j,p_i-p_j)$

于是得到转移方程，总复杂度 $O(L+m^2)$

#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;
}

最后编辑于：2019.08.12 11:18:02