【Codeforces 923E】Perpetual Subtraction

发表于
http://codeforces.com/problemset/problem/923/E

题目链接

【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) $ 。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#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;
}