有一个 n 个数的序列,每一个数在 1 \dotsc D 中随机生成,定义一个序列是合法的当且仅当能取出至少 m 个对子(相同的数),对于 D^n 种可能的序列,求合法序列数。D \leq 10^5, n, m \leq 10^9

羡慕你们能去 CTS 的 [大哭]

先特判掉 n < 2md \leq (n - 2m + 1) 的情况,分别应当输出 0D^n

\{d_i\} 表示 i 这个数在 a_{1 \dotsc n} 中出现了几次。那么假设能够取出 m 对,则 \displaystyle (\sum_{i=1}^D d_i \bmod 2) \leq (n - 2m)。考虑枚举 \displaystyle m = \sum_{i=1}^D d_i \bmod 2,令 \displaystyle F(x) = \sum_{i=0}^\infty [i \bmod 2 = 1] \frac {x^i} {i!}, G(x) = \sum_{i=0}^\infty [i \bmod 2 = 0] \frac {x^i} {i!} ,用生成函数化简得:

ans = \sum_{k=0}^{n-2m} \binom {D} {k} n! [x^n] F^k(x) G^{D-k}(x)

考虑到 \displaystyle F(x) = \frac {e^x - e^{-x}} {2}, G(x) = \frac {e^x + e^{-x}} {2},代入并二项式定理展开

\begin{aligned} ans &= \frac 1 {2^D} \sum_{k=0}^{n-2m} \sum_{i=0}^k \sum_{j=0}^{D-k} [x^n] n! (-1)^{k-i} \binom D k \binom k i \binom {D-k} j e^{x(2i + 2j - D)} \\ &= \frac 1 {2^D} \sum_{k=0}^{n-2m} \sum_{i=0}^k \sum_{j=0}^{D-k} (-1)^{k-i} \binom D k \binom k i \binom {D-k} j (2i + 2j - D)^n \\ &= \frac {D!} {2^D} \sum_{k=0}^{n-2m} \sum_{i=0}^k \sum_{j=0}^{D-k} \frac {(-1)^{k-i} (2i + 2j - D)^n} {i! (k-i)! j! (D-k-j)!} \\ \end{aligned}

这样直接做就是 \mathcal O(D ^ 3) 的了虽然变形一下式子前缀和搞一搞可以优化到 \mathcal O(D ^2) 但是并没有什么卵用,配合其他暴力可以获得 72 pts ... 我也只能自己推到这里。


于是接下来就是看 laofu 和 Itst 题解里的神仙操作了(laofu 的题解推式子讲的太快了,所以下面部分过程是我 yy 的,对正确性不做保证)。

upd 20190517: 因为没去 CTS 不知道 laufu 还发了个 pdf 版的题解 ... 然后 zhihu 上的回答之所以跳得快是因为公式挂掉了 ... 所以上面那句话当我没说 orz ...

对于上面这个式子,我们发现除了 (-1)^{k-i} 以外都与 ij 具体的值无关,只和 i + j 有关。我们稍微变形一下式子:

ans = \frac {D!} {2^D} \sum_{k=0}^{n-2m} \sum_{i+j=0}^{D} \frac {(2(i+j)-D)^n} {(i+j)! (D-i-j)!} \sum_{i=0}^k \frac {(i+j)!} {i! j!} \cdot \frac {(D-i-j)!} {(k-i)! (D-k-j)!} (-1)^{k-i}

考虑 \displaystyle \frac {(x+y)!} {x! y!} = \binom {x+y} x 的组合意义即从 (0, 0) 出发,每次可以向下或向右走一步(即 (+1, 0)(0, +1) ),最后到达 (x, y) 的方案数。

那么式子就转化为从 (0, 0) 走到 (i, j) ,再从 (i, j) 走到 (k, D - k),其中一种方案的权值为 (-1)^{k-i},要求所有方案的权值和。显然我们可以直接从 (0, 0) 走到 (k, D - k)

用一个生成函数来解决「走路」的过程,还是不考虑 (-1)^{k-i},则应当形如

[x^k] (1+x)^D

考虑把 (-1)^{k-i} 放进去,那么

\begin{aligned} ans &= \frac {D!} {2^D} \sum_{i=0}^D \frac {(2i-D)^n} {i! (D-i)!} \sum_{k=0}^{n-2m} [x^k] (1+x)^i (1-x)^{D-i} \\ &= \frac {1} {2^D} \sum_{i=0}^D (2i-D)^n \binom Di \sum_{k=0}^{n-2m} [x^k] (1+x)^i (1-x)^{D-i} \end{aligned}

假设

F(i, D) = \sum_{k=0}^{n-2m}[x^k] (1+x)^i (1-x)^{D-i}

那么

ans = \frac 1 {2^D} \sum_{i=0}^{D} (2i-D)^n \binom D i F(i, D)

也就是说我们需要求得 F(0 \dotsc n, D) ,考虑递推

F(0, 0) = 1 \begin{aligned} F(0, D) &= \sum_{k=0}^{n-2m} [x^k] (1-x)^D \\ &= \sum_{k=0}^{n-2m} (-1)^k \binom D k \\ &= \sum_{k=0}^{n-2m} (-1)^k \left( \binom {D-1} k + \binom {D-1} {k-1} \right) \\ &= \left( \sum_{k=0}^{n-2m} (-1)^k \binom {D-1} k \right) - \left( \sum_{k=0}^{n-2m-1} (-1)^k \binom {D-1} k \right) \\ &= (-1)^{n-2m} \binom {D-1} {n-2m} \end{aligned} \begin{aligned} F(i, D) &= \sum_{k=0}^{n-2m} [x^k] (1+x)^i (1-x)^{D-i} \\ &= \sum_{k=0}^{n-2m} [x^k] (-(1-x) + 2) (1+x)^{i-1} (1-x)^{D-i} \\ &= \sum_{k=0}^{n-2m} [x^k] -\left( (1+x)^{i-1} (1-x)^{D-i+1} \right) + 2\left( 2(1+x)^{i-1} (1-x)^{D-i}\right) \\ &= -F(i - 1, D) + 2 F(i - 1, D - 1) \end{aligned}

那么又回到了之前走格子的问题上,我们可以从 (0, 1 \dotsc D) 中的任何一个点出发并携带 F(0, 1 \dotsc D) 的权值。每次可以有两种移动方式,第一种 (+1, 0) 并使得携带的值乘上 -1,第二种 (+1, +1) 并使得携带的值乘上 2。可以发现每走一步 x 坐标一定会 +1,那么就是从 i 步选了 \Delta y = D - j 步走了 (+1, +1)

\begin{aligned} F(i, D) = \sum_{j=0}^{D} F(0, j) (-1)^{i+j-D} 2^{D-j} \binom i {D-j} \end{aligned}

那么

\begin{aligned} ans &= \frac 1 {2^D} \sum_{i=0}^D (2i-D)^n \binom D i F(i, D) \\ &= \frac 1 {2^D} \sum_{i=0}^D (2i-D)^n \binom D i \sum_{j=0}^D F(0, j) (-1)^{i+j-D} 2^{D-j} \binom i {D-j} \\ &= \frac {(-1)^D D!} {2^D} \sum_{i=0}^D \sum_{j=0}^D \frac {1} {(i + j - D)!} \cdot \frac {(2i - D)^n} {(D-i)!} \cdot \frac {2^{D-j} F(0, j)} {(D-j)!} \end{aligned}

\begin{aligned} f(x) &= \sum_{i=0}^D \frac {(2i - D)^n x^i} {(D-i)!} \\ g(x) &= \sum_{i=0}^D \frac {2^{D-j} F(0, i)x^i} {(D-i)!} \end{aligned}

这样就可以得到

ans = \frac 1 {2^D} \sum_{k=D}^{2D} \frac { [x^k] \left( f(x) \cdot g(x) \right) } {(-1)^k (k-D)!}

直接 NTT 即可。


Itst 的题解提供了另一种思路,可以发现我们直接推式子的瓶颈在于我们有三个 \sum,而最多只能用卷积优化掉一个。那有没有办法优化成只有一个 \sum 呢?答案是有的。我们可以只硬点至少有多少个数的出现次数为奇数,这样另一个生成函数就是 e^x,我们就少用一次二项式定理,\sum 也就少一个。对于这样求出来的答案,反演一下就能得到我们要求的答案。


总结:这是一道好题,可是我什么都不会。

代码:

// =================================
//   author: memset0
//   date: 2019.05.15 10:39:33
//   website: https://memset0.cn/
// =================================
#include <bits/stdc++.h>
#define ll long long
#define debug(...) ((void)0)
#ifndef debug
#define debug(...) fprintf(stderr,__VA_ARGS__)
#endif
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 = 4e5 + 10, mod =  998244353;
int n, m, d, k, ans, lim = 1, inv_lim;
int a[N], b[N], c[N], w[N], rev[N], fac[N], ifac[N];

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 inv(int x) { return x < 2 ? 1 : mul(mod - mod / x, inv(mod % x)); }
inline int C(int n, int m) { return n < m ? 0 : mul(fac[n], mul(ifac[m], ifac[n - m])); }
inline int fpow(int a, int b) { int s = 1; for (; b; b >>= 1, a = mul(a, a)) if (b & 1) s = mul(s, a); return s; }

inline void ntt(int *a) {
    for (int i = 0; i < lim; i++) if (i < rev[i]) std::swap(a[i], a[rev[i]]);
    for (int len = 1; len < lim; len <<= 1)
        for (int i = 0; i < lim; i += (len << 1))
            for (int j = 0; j < len; j++) {
                int x = a[i + j], y = mul(w[j + len], a[i + j + len]);
                a[i + j] = inc(x, y), a[i + j + len] = dec(x, y);
            }
}

inline int F(int d) {
    if (d == 0) return 1;
    return mul((n - 2 * m) & 1 ? mod - 1 : 1, C(d - 1, n - m * 2));
}

void main() {
    read(d), read(n), read(m);
    if (n < (m << 1)) { puts("0"); return; }
    if (d <= (n - (m << 1) + 1)) { print(fpow(d, n), '\n'); return; }
    while (lim <= (d << 1)) lim <<= 1, ++k; inv_lim = inv(lim);
    fac[0] = fac[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++) ifac[i] = mul(mod - mod / i, ifac[mod % i]);
    for (int i = 2; i < lim; i++) ifac[i] = mul(ifac[i - 1], ifac[i]);
    for (int i = 0; i < lim; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (k - 1));
    for (int wn, len = 1; len < lim; len <<= 1) {
        wn = fpow(3, (mod - 1) / (len << 1)), w[len] = 1;
        for (int i = 1; i < len; i++) w[i + len] = mul(w[i + len - 1], wn);
    }
    for (int i = 0; i <= d; i++) a[i] = mul(fpow(dec(inc(i, i), d), n), ifac[d - i]);
    for (int i = 0; i <= d; i++) b[i] = mul(fpow(2, d - i), mul(ifac[d - i], F(i)));
    // print(a, 0, d, "a"), print(b, 0, d, "b");
    ntt(a), ntt(b);
    for (int i = 0; i < lim; i++) a[i] = mul(a[i], b[i]);
    std::reverse(a + 1, a + lim), ntt(a);
    for (int i = 0; i <= (d << 1); i++) c[i] = mul(a[i], inv_lim);
    for (int i = d; i <= (d << 1); i++) ans = inc(ans, mul(c[i], mul(ifac[i - d], i & 1 ? mod - 1 : 1)));
    // print(c, 0, d << 1, "c");
    print(mul(ans, mul(mul(fac[d], d & 1 ? mod - 1 : 1), inv(fpow(2, d)))), '\n');
}

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

生成函数 巧妙的思路 容斥

已有 3 条评论

  1. smy smy

    您怎么什么都会啊.jpg

    我被这题秒了qwq

  2. 只会 12 分的蒟蒻哭了

    您怎么什么都会啊.jpg

    (建议把打错的 laofu 名字修正一下(((

  3. 什么都不会+1

洛谷5363 [SDOI2019]移动金币
上一篇 «
洛谷5305 [GXOI/GZOI2019]旧词
» 下一篇