【Codeforces 923E】Perpetual Subtraction

题目链接

【Codeforces 923E】Perpetual Subtraction

做法

设当前取到 $i \in [0, n]$ 的概率生成函数为 $f(x)$ ， 下一步后为 $F(x)$ ，则：

$$F(x) = \sum_{ i = 0 }^{ n }{ x^i \sum_{ j = 0 }^{ n }{ \frac{ [x^j] f(x) }{ j + 1 } } }$$ $$= \sum_{ j = 0 }^{ n }{ \frac{ [x^j] f(x) }{ j + 1 } \frac{ x^{ j + 1 } - 1 }{ x - 1 } }$$ $$= \frac{ 1 }{ x-1 } { \sum_{ j = 0 }^{ n } [x^j] f(x) \int_{ 1 }^{ x } t^j { \rm d } t }$$ $$= \frac{ \int_{ 1 }^{ x } f(t) { \rm d } t }{ x - 1 }$$

令 $g(x) = f(x + 1)$ ，则：

$$G(x) = F(x + 1) = \frac{ \int_{ 0 }^{ x } g(t) { \rm d } t }{ x }$$ $$[x^i] G(x) = \frac{ [x^i] g(x) }{ i + 1 }$$ $m$ 次操作后 $[x^i] G(x) = \frac{ [x^i] g(x) }{ (i + 1)^m }$

已知 $[x^i] f(x)$ 求 $[x^i] g(x)$ ：

$$\sum_{ i = 0 }^{ n }{ g_i x^i } = \sum_{ i = 0 }^{ n }{ f_j (x + 1)^j } = \sum_{ j = 0 }^{ n }{ f_j \sum_{ i = 0 }{ j }{ C(j, i) x^i } }$$ $$g_i = \sum_{ j = i }^{ n }{ C(j, i)f_j }$$ $$i! g_i = \sum_{ j = i }^{ n }{ \frac{ j! f_j }{ (j - i)! } }$$

已知 $[x^i] g(x)$ 求 $[x^i] f(x)$ ：

$$i! f_i = \sum_{ j=1 }^{ n }{ \frac{ j! f_j }{ (-1)^{ j - i }( j - i )! } }$$ $NTT$ 卷积即可。时间复杂度 $O(n \log n)$ 。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353, N = 200010;

inline int add(const int &x, const int &y) {
	return x + y < mod ? x + y : x + y - mod;
}
inline int sub(const int &x, const int &y) {
	return x - y < 0 ? x - y + mod : x - y;
}
inline int mul(const int &x, const int &y) { return(int)((ll)x * y % mod); }
int ksm(int x, ll y = mod - 2) {
	int ss = 1; for(; y; y /= 2, x = mul(x, x)) if(y % 2) ss = mul(ss, x);
	return ss;
}
namespace Poly {
	int Get(int x) { int ss = 1; for(; ss <= x; ss <<= 1); return ss; }
	void ntt(vector<int> &A, int lmt, int opt) {
		A.resize(lmt);
		for(int i = 0, j = 0; i < lmt; i++) {
			if(i < j) swap(A[i], A[j]);
			for(int k = lmt >> 1; (j ^= k) < k; k >>= 1);
		}
		vector<int> w(lmt >> 1);
		for(int mid = 1; mid < lmt; mid <<= 1) {
			w[0] = 1;
			int w0 = ksm(opt == 1 ? 3 : (mod + 1) / 3, (mod - 1) / mid / 2);
			for(int j = 1; j < mid; j++) w[j] = mul(w[j - 1], w0);
			for(int j = 0; j < lmt; j += mid << 1)
				for(int k = 0; k < mid; k++) {
					int x = A[j + k], y = mul(w[k], A[j + mid + k]);
					A[j + k] = add(x, y), A[j + mid + k] = sub(x, y);
				}
		}
		if(opt == -1)
			for(int inv = ksm(lmt), i = 0; i < lmt; i++)
				A[i] = mul(A[i], inv);
	}
	vector<int> Mul(const vector<int> &a, const vector<int> &b) {
		vector<int> A = a, B = b; int lmt = Get(a.size() + b.size() - 2);
		ntt(A, lmt, 1), ntt(B, lmt, 1);
		for(int i = 0; i < lmt; i++) A[i] = mul(A[i], B[i]);
		ntt(A, lmt, -1); return A.resize(a.size() + b.size() - 1), A;
	}
}

int n; ll m;
vector<int> f, g;
int fa[N], fb[N];

int main() {
	scanf("%d%I64d", &n, &m);
	fa[0] = fa[1] = fb[0] = fb[1] = 1;
	for(int i = 2; i <= n; i++) fa[i] = mul(fa[i - 1], i);
	for(int i = 2; i <= n; i++) fb[i] = mul(mod - mod / i, fb[mod % i]);
	for(int i = 2; i <= n; i++) fb[i] = mul(fb[i - 1], fb[i]);
	f.resize(n + 1), g.resize(n + 1);
	for(int i = 0; i <= n; i++)
		scanf("%d", &f[n - i]), f[n - i] = mul(f[n - i], fa[i]), g[i] = fb[i];
	g = Poly::Mul(f, g), g.resize(n + 1);
	for(int i = 0; i <= n; i++) g[n - i] = mul(g[n - i], ksm(ksm(i + 1, m)));
	for(int i = 0; i <= n; i++) f[i] = (i & 1) ? (mod - fb[i]) : fb[i];
	f = Poly::Mul(f, g);
	for(int i = 0; i <= n; i++) printf("%d ", mul(f[n - i], fb[i]));
	return 0;
}