山有木兮木有枝
心悦君兮君不知

被同学拉去做其他的题了咕掉了考试

假设用 f(a, b) 表示长度为 a ,有 b 个黑色珠子的且满足首位连接后没有超过 k 个连续黑色珠子的方案数,设 g(x) = f(n / x, m / x) ,可以通过 Burnside 引理证明 ans = \sum\limits_{i=1}^n g(n / \gcd(i, n))

考虑 f(a, b) 相当于求方程组

x_0 + x_1 + ... + x_{a - b} = b(0 \leq x_i \leq k, 0 \leq x_0 + x_{a - b} \leq k)

的解的个数,可以转换为生成函数,即

\begin{aligned} f(a, b) &= [x^b] \left(\sum_{i = 0}^{k} x^i\right) ^ {a - b - 1} \left( \left(\sum_{i = 0}^{k} x^i\right)^2{\rm mod}\ x^{k + 1}\right) \\ &= [x^b] \left(\sum_{i = 0}^{k} x^i\right) ^ {a - b - 1} \left(\sum_{i = 0}^{k} (i +1)x^i\right)\\ &= [x^b]\left(\frac{1 - x^{k + 1}}{1 - x}\right) ^ {a - b - 1} \frac{1 - (k + 2)x^{k + 1} + (k + 1)x^{k + 2}}{(1 - x)^2}\\ &= [x^b] \left(1 - x^{k + 1}\right) ^ {a - b - 1} \left(1 - x \right) ^ {-(a - b + 1)} \left(1 - (k + 2)x^{k + 1} + (k + 1)x^{k + 2} \right) \end{aligned}

其中第一个可以直接二项式定理展开,第二个需要考虑广义二项式定理

(a+b)^{-n} = \sum_{i=0}^{\infty} \binom {-n} i a^i b^{-n-i}

我们求一个形如 \binom {-n} m 的式子,即

\begin{aligned} \binom {-n} m &= \dfrac {(-n)(-n-1)(-n-2)...(-n-m+1)} {m!} \\ &= \dfrac {(-1)^m n(n+1)(n+2)...(n+m-1)} {m!} \\ &= \bigg(-1 \bigg)^m \binom {n+m-1} {m} \end{aligned}

那么

\begin{aligned} (1-x)^{-n} &= (-1)^{-n} (x-1)^{-n} \\ &= (-1)^{n} \sum_{i=0}^{\infty} (-1)^i \binom {n+i-1} i x^i (-1)^{-n-i} \\ &= \sum_{i=0}^{\infty} \binom {n+i-1} i x^i \end{aligned}

最后可以化简为

\small{f(a, b) = [x^b]\left(\sum_{i = 0}^{\infty}\binom{a - b - 1}{i}(-1)^ix^{(k + 1)i}\right)\left(\sum_{j = 0}^{\infty}\binom{a - b + j}{j}x^j\right)(1 - (k + 2)x^{k + 1} + (k + 1)x^{k + 2})}

考虑直接计算

\begin{aligned} f(a, b) = \sum_{(k + 1)i + j = b} &(-1)^i\binom{a - b - 1}{i}\binom{a - b+ j}{j} \\ - (k + 2) \sum_{(k + 1)i + j = b - k - 1} &(-1)^i\binom{a - b - 1}{i}\binom{a - b+ j}{j} \\ + (k + 1) \sum_{(k + 1)i + j = b - k - 2} &(-1)^i\binom{a - b - 1}{i}\binom{a - b+ j}{j} \end{aligned}

枚举 i 之后,我们可以直接算出 j ,单次时间复杂度 O(\frac b {k-1})

代码:

// =================================
//   author: memset0
//   date: 2019.03.14 12:34:53
//   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; register char c = getchar(); register 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); }

const int N = 1e5 + 10, mod = 998244353;
int n, m, k, ans, f[N], fac[N << 1], ifac[N << 1];

inline int dec(int a, int b) { a -= b; return a < 0 ? a + mod : a; }
inline int sub(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 : (ll)(mod - mod / x) * inv(mod % x) % mod; }
inline int C(int n, int m) { return n < m ? 0 : mul(fac[n], mul(ifac[m], ifac[n - m])); }

inline int calc(int n, int m) {
    int ans = 0, sum = 0;
    for (int i = 0, j; j = m - (k + 1) * i, j >= 0; i++)
        sum = sub(sum, mul(i & 1 ? mod - 1 : 1, mul(C(n - m - 1, i), C(n - m + j, j))));
    ans = sub(ans, sum), sum = 0;
    for (int i = 0, j; j = m - k - 1 - (k + 1) * i, j >= 0; i++)
        sum = sub(sum, mul(i & 1 ? mod - 1 : 1, mul(C(n - m - 1, i), C(n - m + j, j))));
    ans = dec(ans, mul(sum, k + 2)), sum = 0;
    for (int i = 0, j; j = m - k - 2 - (k + 1) * i, j >= 0; i++)
        sum = sub(sum, mul(i & 1 ? mod - 1 : 1, mul(C(n - m - 1, i), C(n - m + j, j))));
    return sub(ans, mul(sum, k + 1));
}

void main() {
    read(n), read(m), read(k);
    fac[0] = fac[1] = ifac[0] = ifac[1] = 1;
    for (int i = 2; i <= (n << 1); i++) fac[i] = mul(fac[i - 1], i);
    for (int i = 2; i <= (n << 1); i++) ifac[i] = mul(mod - mod / i, ifac[mod % i]);
    for (int i = 2; i <= (n << 1); i++) ifac[i] = mul(ifac[i - 1], ifac[i]);
    for (int l = 1; l <= n; l++)
        if (n % l == 0 && m % l == 0)
            f[l] = calc(n / l, m / l);
    for (int i = 1; i <= n; i++) ans = sub(ans, f[n / std::__gcd(n, i)]);
    print(mul(ans, inv(n)), '\n');
}

} signed main() { return ringo::main(), 0; }

生成函数 Polya 定理

已有 7 条评论

  1. 洛谷6519是啥啊qwq

  2. QAQ为什么没有代码高亮(;′⌒`)

  3. 排版令人惊讶qwq

BZOJ3684 大朋友和多叉树
上一篇 «
洛谷3732 [HAOI2017]供给侧改革
» 下一篇