VK Cup 2018 - Round 1 E Perpetual Subtraction

题目描述

http://codeforces.com/problemset/problem/923/E

简要题意：你现在有一个整数 $x$，题目给出它属于 $[0,n]$ 中某个数的概率，现在要进行 $m$ 次随机，每次随机将等概率的将 $x$ 变成 $[0,x]$ 中的任意一个整数，求 $m$ 次操作后，整数 $x=k$，其中 $k\in [0,n]$ 的概率

$n\le {10}^5,m\le {10}^{18}$

Solution

我们令 $f_{k,i}$ 表示进行了 $k$ 次随机之后为 $i$ 的概率，容易得到 $f_{k,i}=\sum _{j=i}^n\frac{f_{k-1,j}}{j+1}$，发现这个东西是一个线性变换，尝试用生成函数搞一下，我们将其写成生成函数的形式，得到 $F_k(x)=\sum _{i=0}^n{f}_{k,i}{x}^i$，然后尝试化简一下

$$\begin{array}{rl}{F}_k(x)& =\sum _{i=0}^n{f}_{k,i}{x}^i\\ & =\sum _{i=0}^n{x}^i\sum _{j=i}^n\frac{f_{k-1,j}}{j+1}\\ & =\sum _{j=0}^n\frac{f_{k-1,j}}{j+1}\sum _{i=0}^j{x}^i\\ & =\sum _{j=0}^n\frac{f_{k-1,j}}{j+1}\frac{x^{j+1}-1}{x-1}\\ & =\frac{1}{x-1}\sum _{j=0}^n{f}_{k-1,j}\frac{x^{j+1}-1}{j+1}\\ & =\frac{1}{x-1}\sum _{i=0}^n{f}_{k-1,i}{\int }_1^x{t}^i\mathrm{d}\mathrm{t}\\ & =\frac{1}{x-1}{\int }_1^x(\sum _{i=0}{f}_{k-1,i}{t}^i)\mathrm{d}\mathrm{t}\\ & =\frac{1}{x-1}{\int }_1^x{F}_{k-1}(t)\mathrm{d}\mathrm{t}\end{array}$$

现在似乎有点眉目了，但是这个 $\frac{1}{x-1}$ 和这个从 $1$ 积到 $x$ 的积分不是很好应对，我们令 $G_k(x)=F_k(x+1)$，然后在带进这个式子里去，$G_k(x)=\frac{1}{x}{\int }_1^{x+1}{F}_{k-1}(t)\mathrm{d}\mathrm{t}=\frac{1}{\mathrm{x}}{\int }_0^{\mathrm{x}}{\mathrm{F}}_{\mathrm{k}-1}(\mathrm{t}+1)\mathrm{d}\mathrm{t}$，我们注意到 $G_{k-1}(x)=F_{k-1}(x+1)$，那么我们就能得到 $G_k(x)=\frac{1}{x}{\int }_0^x{G}_{k-1}(x)\mathrm{d}\mathrm{t}=\sum _{\mathrm{i}=0}^{\mathrm{n}}\frac{1}{\mathrm{i}+1}{\mathrm{g}}_{\mathrm{k}-1,\mathrm{i}}{\mathrm{x}}^{\mathrm{i}}$，也就是说 $g_{k,i}=\frac{1}{(i+1{)}^k}{g}_{0,i}$，然后我们只需要求一下 $F_0(x)$ 到 $G_0(x)$ 的转换和 $G_m(x)$ 到 $F_m(x)$ 的转换，推一下能发现都是一个差卷积的形式，时间复杂度 $O(n\log n)$

#include <iostream>
#include <vector>
#include <algorithm>
#define maxn 100010
#define ll long long
using namespace std;

const int p = 998244353;

ll pow_mod(ll x, ll n) {
    ll s = 1;
    for (; n; n >>= 1, x = x * x % p)
        if (n & 1) s = s * x % p;
    return s;
}

typedef std::vector<int> Poly;
namespace Pol {
    inline int add(int a, int b) { return (a += b) >= p ? a -= p : a; }
    inline int mul(int a, int b) { return 1ll * a * b % p; } 
 
    const int N = 4200000;
    int a[N], b[N];
 
    int P[N];
    void init_P(int n) {
        int l = 0; while ((1 << l) < n) ++l;
        for (int i = 0; i < n; ++i) P[i] = (P[i >> 1] >> 1) | ((i & 1) << l - 1);
    }
    void NTT(int *a, int n, int type) {
        static int w[N]; ll G = 3, Gi = pow_mod(G, p - 2);
        for (int i = 0; i < n; ++i) if (i < P[i]) swap(a[i], a[P[i]]);
        for (int i = 2, m = 1; i <= n; m = i, i *= 2) {
            int wn = pow_mod(type > 0 ? G : Gi, (p - 1) / i);
            w[0] = 1; for (int j = 1; j < m; ++j) w[j] = mul(wn, w[j - 1]);
            for (int j = 0; j < n; j += i)
                for (int k = 0; k < m; ++k) {
                    int t1 = a[j + k], t2 = mul(a[j + k + m], w[k]);
                    a[j + k] = add(t1, t2);
                    a[j + k + m] = add(t1, p - t2);
                }
        }
        if (type < 0) {
            ll inv = pow_mod(n, p - 2);
            for (int i = 0; i < n; ++i) a[i] = inv * a[i] % p;
        }
    }
    Poly Mul(const Poly &A, const Poly &B, int n1, int n2) {
        int n = 1; while (n < n1 + n2 - 1) n <<= 1; init_P(n);
        for (int i = 0; i < n1; ++i) a[i] = add(A[i], p);
        for (int i = 0; i < n2; ++i) b[i] = add(B[i], p);
        fill(a + n1, a + n, 0), fill(b + n2, b + n, 0);
        NTT(a, n, 1); NTT(b, n, 1);
        for (int i = 0; i < n; ++i) a[i] = mul(a[i], b[i]);
        NTT(a, n, -1); Poly ans(n1 + n2 - 1); copy_n(a, n1 + n2 - 1, ans.begin());
        return ans;
    }
}  // namespace Pol

int n;
ll m, fac[maxn], inv[maxn];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m; ++n; Poly A(n), B(n);
    fac[0] = 1; for (int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i % p;
    inv[n] = pow_mod(fac[n], p - 2); for (int i = n - 1; ~i; --i) inv[i] = inv[i + 1] * (i + 1) % p; 
    for (int i = 0; i < n; ++i) cin >> A[i], A[i] = A[i] * fac[i] % p; 
    for (int i = 0; i < n; ++i) B[i] = inv[i];
    reverse(A.begin(), A.end()); A = Pol::Mul(A, B, n, n); A.resize(n); reverse(A.begin(), A.end());
    for (int i = 0; i < n; ++i) A[i] = A[i] * inv[i] % p * pow_mod(pow_mod(i + 1, m), p - 2) % p;
    for (int i = 0, sgn = 1; i < n; ++i, sgn = -sgn) A[i] = A[i] * sgn * fac[i] % p;
    reverse(A.begin(), A.end()); A = Pol::Mul(A, B, n, n); A.resize(n); reverse(A.begin(), A.end());
    for (int i = 0, sgn = 1; i < n; ++i, sgn = -sgn)
        cout << (A[i] * sgn * inv[i] % p + p) % p << " \n"[i == n - 1];
    return 0;
}