当我跨过沉沦的一切
向着永恒开战的时候
你是我的军旗

一枚棋子要从 (0,0) 跳到 (T_x,T_y)。每一步只能向右上方跳,且横坐标变化不能超过 M_x,纵坐标变化不能超过 M_y,每一次跳跃不能停留在原地。

K 个向量是非法的,这些向量形如 (k_i,k_i) ,会在读入中给出。也就是说,每一步 x,y 的增量不能同时等于 k_i所有的 k_i 都是 G 的倍数。

求从 (0,0),跳恰好 R 步到 (T_x,T_y) 的方案数。答案对 10^9+7 取模。

T,M \leq 10^6,\ R \leq 1000,\ 10000 \leq G \leq 50000,\ K \leq 50

先考虑 K = 0 的情况。我们显然需要将 x 轴和 y 轴分开考虑。但是考虑到 x 轴和 y 轴不能同时只增长 0 ,这个就可以二项式反演了。定义 f_i 表示恰好出现 i(0, 0) 的方案数,g_i 表示至少出现 i(0, 0) 的方案数,也就是题目给我们的 R 只能用 R - i 次。显然

\binom R k g_k = \sum_{i=k}^R \binom i k f_i \Leftrightarrow f_k = \sum_{i=k}^R (-1)^{k-i} \binom i k \binom R i g_i

ans = f_0 ,我们只需要求出 \{g_i\}_{i=0}^R 即可。

这个东西显然可以直接卷一下 \forall k \in [0, R] ,\; \left( \sum_{i=0}^M x^i \right)^k ,然而这个东西显然会让你 get TLE ,考虑有没有什么优秀的方法。

再次考虑容斥,用 f'_i 表示恰好有 i 步超出限制,g'_i 表示至少 i 步超出限制。显然

g'_k = \sum_{i=k}^R \binom i k f'_i \Leftrightarrow f'_k = \sum_{i=k}^R (-1)^{k-i} \binom i k g;_i

g_iR = i 时的 f'_0 。这个 g'_i 就比较好求了,可以插板法,我们硬点一些箱子至少选 M + 1 ,另一些至少选 0 个。7

以上部分的时间复杂度是 O(R^2) 的,也可以通过 60\% 的数据。


下面考虑 K \neq 0 怎么做了。发现我们照样可以枚举一下总共是有多少步的 G ,同样可以像上面一样二项式反演。

时间复杂度 O\left( R^2 \left\lfloor \frac {T} {G} \right\rfloor \right) ,是 10^8 级别的,可以跑进去。

注意处理一下逆元什么的避免凭空多个 \log 出来翻车。

代码

// =================================
//   author: memset0
//   date: 2019.07.20 23:28:36
//   website: https://memset0.cn/
// =================================
#include <bits/stdc++.h>
#define ll long long
#define rep(i, l, r) for (int i = (l), i##ed = (r); i <= i##ed; ++i)
#define for_each(i, a) for (size_t i = 0, i##ed = a.size(); i < i##ed; ++i)
namespace ringo {

template <class T> inline void read(T &x) {
    x = 0; char c = getchar(); bool f = 0;
    while (!isdigit(c)) f ^= c == '-', c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
    if (f) x = -x;
}
template <class T> inline void print(T x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) print(x / 10);
    putchar('0' + x % 10);
}
template <class T> inline void print(T x, char c) { print(x), putchar(c); }
template <class T> inline void print(T a, int l, int r, std::string s = "") {
    if (s != "") std::cout << s << ": ";
    for (int i = l; i <= r; i++) print(a[i], " \n"[i == r]);
}

const int N = 1e6 + 10, M = 110, P = 1e4 + 10, mod = 1e9 + 7;
int R, G, K, Tx, Ty, Mx, My, ans, a[M];
int F[M][P], Gx[N], Gy[N], T[P], cnt[P], tmp[P], fac[N << 1], inv[N << 1], ifac[N << 1];

inline int tpow(int x) { return x & 1 ? mod - 1 : 1; }
inline int dec(int a, int b) { a -= b; return a < 0 ? a + mod : a; }
inline int inc(int a, int b) { a += b; return a >= mod ? a - mod : a; }
inline int mul(int a, int b) { return (ll)a * b - (ll)a * b / mod * mod; }
inline int binom(int n, int m) { return n < m ? 0 : mul(fac[n], mul(ifac[m], ifac[n - m])); }
inline int board(ll n, int m) { return n < m ? 0 : binom(n - 1, m - 1); }

void init_fac(int lim) {
    fac[0] = fac[1] = inv[0] = inv[1] = ifac[0] = ifac[1] = 1;
    for (int i = 2; i <= lim; i++) fac[i] = mul(fac[i - 1], i);
    for (int i = 2; i <= lim; i++) inv[i] = mul(mod - mod / i, inv[mod % i]);
    for (int i = 2; i <= lim; i++) ifac[i] = mul(ifac[i - 1], inv[i]);
}

void calc(int f) {
    F[f][0] = (Tx - f * G == 0) && (Ty - f * G == 0);
    for (int i = 1; i <= R; i++) {
        // 走 i 步能到达的 => F[f][i] (反演前)
        for (int j = 0; j <= i; j++) {
            // 其中 j 步不合法 => Gx[j] / Gy[j];
            Gx[j] = mul(board(Tx - f * G + i - (ll)(Mx + 1) * j, i), binom(i, j));
            Gy[j] = mul(board(Ty - f * G + i - (ll)(My + 1) * j, i), binom(i, j));
            // printf("%d %d %d -> (x %d) (y %d)\n", f, i, j, Gx[j], Gy[j]);
        }
        int Rx = 0, Ry = 0;
        for (int j = 0; j <= i; j++) {
            Rx = inc(Rx, mul(tpow(j), Gx[j]));
            Ry = inc(Ry, mul(tpow(j), Gy[j]));
        }
        // printf("%d %d -> %d %d\n", f, i, Rx, Ry);
        F[f][i] = mul(Rx, Ry);
    }
    // printf("[%d] ", f), print(F[f], 0, R);
    // 反演 F[f]
    // F[f][0] = 1;
    for (int i = R; i >= 0; i--)
        for (int j = 0; j < i; j++)
            F[f][i] = inc(F[f][i], mul(tpow(i + j), mul(binom(i, j), F[f][j])));
    // printf("[%d] ", f), print(F[f], 0, R);
}

void main() {
    read(Tx), read(Ty), read(Mx), read(My), read(R), read(G), read(K);
    for (int i = 1; i <= K; i++) read(a[i]);
    std::sort(a + 1, a + K + 1);
    K = std::unique(a + 1, a + K + 1) - a - 1;
    init_fac(std::max(Tx, Ty) + R);
    int lim = std::min(Tx, Ty) / G;
    for (int i = 0; i <= lim; i++) calc(i);
    cnt[0] = 1;
    for (int i = 0; i <= R && i <= lim; i++) {
        if (i) {
            // DP 方案数数组递推下一步
            for (int i = 0; i <= lim; i++)
                tmp[i] = cnt[i], cnt[i] = 0;
            for (int k = 1; k <= K; k++)
                for (int j = lim - a[k] / G; j >= 0; j--)
                    cnt[j + a[k] / G] = inc(tmp[j], cnt[j + a[k] / G]);
        }
        // print(cnt, 0, lim);
        for (int j = 0; j <= lim; j++) {
            // printf("%d %d : %d\n", i, j, mul(binom(R, i), mul(F[j][R - i], cnt[j])));
            T[i] = inc(T[i], mul(binom(R, i), mul(F[j][R - i], cnt[j])));
        }
    }
    // print(T, 0, R);
    for (int i = 0; i <= R; i++)
        ans = inc(ans, mul(tpow(i), T[i]));
    print(ans, '\n');
}

} signed main() {
#ifdef memset0
    freopen("1.in", "r", stdin);
#endif
    return ringo::main(), 0;
}

巧妙的思路 二项式反演 隔板法 Favorite

已有 2 条评论

  1. iiintoCalm iiintoCalm

    我们这的题怎么tmd还被上传到LOJ来了 8过这好像是dwj鸽鸽出的题?

    1. 这个就不清楚了...我也不是在 LOJ 上遇到的。

LOJ6035 「雅礼集训 2017 Day4」洗衣服
上一篇 «
LOJ6051 「雅礼集训 2017 Day11」PATH
» 下一篇