CF1278F Cards 加强版

· · 个人记录

题解区没有 Binomial Sum 的做法，我来写一篇题解。

为了让文章短一点，我删去了部分过程，如果对推导过程有问题或指出错误可以私信我 qwq。

假设读者已经做过了原题，于是有：

\sum_{i=0}^{n}\binom{n}{i}\frac{(m-1)^{n-i}}{m^n}i^k\\

对于类二项式定理的题目，i 放在指数上会较为方便。

对于 i^k，比较常见的思路是利用斯特林数展开，其它题解已经写了，这里不作描述。

还有就是利用 e^x 的泰勒展开式将 i 放到指数上，具体的，就是：

e^x = \sum_{n \geq 0}\frac{x^n}{n!}\\ i^k = k![x^k]e^{ix}

回代原式，有：

=k![x^k]\frac{(m-1)^{n}}{m^n}\sum_{i=0}^{n}\binom{n}{i}e^{ix}(m-1)^{-i}\\

为方便，设 q = \frac{1}{m-1}。

=k![x^k]\frac{(m-1)^{n}}{m^n}\sum_{i=0}^{n}\binom{n}{i}e^{ix}q^{i}\\ =\frac{(m-1)^{n}}{m^n}k![x^k](1+qe^x)^n

设 f(x)=(1+qx)^n，g(x)=e^x。

=\frac{(m-1)^{n}}{m^n}k![x^k]f(g(x))

于是可以令 h(x + 1) = f(x + 1) \pmod{x^{k+1}}。

=\frac{(m-1)^{n}}{m^n}k![x^k]h(g(x))\\ =\frac{(m-1)^{n}}{m^n}\sum_{i=0}^{k}([x^i]h(x))i^k\\

求 h

对 f(x) = (1 + qx)^n，有：

nqf(x) - (1+qx)f'(x) = 0\\ nqf(x + 1) - (1+q(x+1))(f' \circ (x + 1)) = 0\\ nqf(x + 1) - (1+q(x+1))(f \circ (x + 1))' = 0\\ $$ nqh(x+1) - (1+q)h(x+1)' - qxh(x+1)' = D(x+1) = (1+q)x^k(k+1)([x^{k+1}]f(x+1))\\ nqh(x) - (1+q)h(x)' - q(x-1)h(x)' = D(x) = (1+q)(x-1)^k(k+1)([x^{k+1}]f(x+1)) $$ 提取系数： $$ nqh_i - (1+q)(i+1)h_{i+1} - qih_i + q(i+1)h_{i+1} = D_i\\ ih_{i} = (n-i+1)qh_{i-1} - D_{i-1}\\ $$ 就得到了 $h$ 系数的递推式了，但他不能处理 $h_0$。 --- ### 扰动因子 $D D(x) = (1+q)(x-1)^k(k+1)([x^{k+1}]f(x+1))\\ D_i = (1+q)(k+1)([x^{k+1}]f(x+1)) \times \binom{k}{i}(-1)^{k-i}

还有 ([x^{k+1}]f(x+1))：

[x^{k+1}]f(x+1)\\ =[x^{k+1}](1+q(x+1))^{n}\\ =[x^{k+1}]\sum_{j=0}^{n}x^j\sum_{i=j}^{n}\binom{n}{i}q^i\binom{i}{j}\\ =\sum_{i=k+1}^{n}\binom{n}{i}q^i\binom{i}{k+1}\\ =\binom{n}{k+1}\sum_{i=k+1}^{n}\binom{n-k-1}{i-k-1}q^i\\ =\binom{n}{k+1}q^{k+1}(1+q)^{n-k-1}\\

最后是 h_0 的计算，这个直接代入 h(x+1) = f(x+1) \pmod{x^{k+1}}：

h(x+1) = (1+q(x+1))^n \pmod{x^{k+1}}\\ h(x+1) = \sum_{i=0}^{n}\binom{n}{i}q^i(x+1)^i \pmod{x^{k+1}}\\ h(x+1) = \sum_{j=0}^{k}x^j\binom{n}{j}q^j(1+q)^{n-j}\\ h(x) = \sum_{j=0}^{k}\binom{n}{j}q^j(1+q)^{n-j}\sum_{l=0}^j\binom{j}{l}x^l(-1)^{j-l}\\ h(x) = \sum_{l=0}^{k}x^l\sum_{j=l}^{k}\binom{n}{j}q^j(1+q)^{n-j}\binom{j}{l}(-1)^{j-l}\\ h(0) = \sum_{j=0}^{k}\binom{n}{j}q^j(1+q)^{n-j}(-1)^{j} = (1+q)^n\sum_{j=0}^{k}\binom{n}{j}(-\frac{q}{1+q})^j

然后没了。

代码丑：

#include <bits/stdc++.h>
const int mod = 998244353;
using namespace std;
int fac[10000015], ifac[10000015], id[10000015];
int pri[10000015], cnt;
bool vis[10000015];
int dn[10000015];
int fpow(int a, int b = mod - 2)
{
    int r = 1;
    while (b)
    {
        if (b & 1)
            r = 1LL * r * a % mod;
        a = 1LL * a * a % mod;
        b >>= 1;
    }
    return r;
}
void init(int n, int k)
{
    fac[0] = ifac[0] = fac[1] = ifac[1] = id[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        fac[i] = 1LL * fac[i - 1] * i % mod;
        if (!vis[i])
        {
            pri[++cnt] = i;
            id[i] = fpow(i, k);
        }
        for (int j = 1; j <= cnt; j++)
        {
            if (1LL * i * pri[j] >= n)
                break;
            vis[i * pri[j]] = 1;
            id[i * pri[j]] = 1LL * id[i] * id[pri[j]] % mod;
            if (i % pri[j] == 0)
            {
                break;
            }
        }
    }
    ifac[n] = fpow(fac[n]);
    for (int i = n - 1; i >= 2; i--)
        ifac[i] = 1LL * ifac[i + 1] * (i + 1) % mod;
}
inline int C(int n, int m)
{
    if (n < m || m < 0)
        return 0;
    return 1LL * fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
inline int inv(int n)
{
    return 1LL * fac[n - 1] * ifac[n] % mod;
}
int n, m, k, q;
inline int Cn(int m)
{
    if (n < m || m < 0)
        return 0;
    return 1LL * dn[m] * ifac[m] % mod;
}
int f,fk1;
inline int d(int i)
{
    int res = 1LL * (1 + q) * (k + 1) % mod * fk1 % mod * C(k, i) % mod;
    if ((k - i) & 1)
        res = (mod - res) % mod;
    return res;
}
signed main()
{
    cin >> n >> m >> k;
    if (m == 1)
    {
        cout << fpow(n, k);
        return 0;
    }
    init(k + 10, k);
    int ans = 0;
    q = fpow(m - 1);
    dn[0] = 1;
    for (int i = 1; i <= k + 1; i++)
        dn[i] = 1LL * dn[i - 1] * (n - i + 1) % mod;
    if (n <= k + 10)
    {
        int lk = 1LL * fpow(m - 1, n) % mod * fpow(fpow(m, n)) % mod;
        int inv = fpow(m - 1);
        for (int i = 0; i <= n; i++)
        {
            ans = (ans + 1LL * C(n, i) * lk % mod * id[i] % mod) % mod;
            lk = 1LL * lk * inv % mod;
        }
        cout << ans;
        return 0;
    }
    fk1 = 1LL * Cn(k + 1) * fpow(q, k + 1) % mod * fpow(q + 1, n - k - 1) % mod;
    int t1 = 1, t2 = 1, nd = fpow(1 + q);
    for (int i = 0; i <= k; i++)
    {
        int tmp = 1LL * t1 * Cn(i) % mod * t2 % mod;
        if (i & 1)
            tmp = (mod - tmp) % mod;
        f = (f + tmp) % mod;
        t1 = 1LL * t1 * q % mod;
        t2 = 1LL * t2 * nd % mod;
    }
    f = 1LL * f * fpow(1 + q, n) % mod;
    for (int i = 1; i <= k; i++)
    {
        f = (1LL * (n - i + 1) * q % mod * f % mod - d(i - 1) + mod) % mod;
        f = 1LL * f * inv(i) % mod;
        ans = (ans + 1LL * f * id[i] % mod) % mod;
    }
    ans = 1LL * ans * fpow(1LL * (m - 1) * fpow(m) % mod, n) % mod;
    cout << ans;
    return 0;
}