【luogu5245】【模板】多项式快速幂

发表于
https://www.luogu.org/problemnew/show/P5245

题目链接

【luogu5245】【模板】多项式快速幂

做法

这道题直接套快速幂被针对了。。。
考虑将多项式求 $ \ln $ 后乘上原指数再 $ \exp $ 回去等同于求幂。
直接放多项式全家桶了。。。 

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;

inline int Max(int x, int y) { return x > y ? x : y; }
inline int Min(int x, int y) { return x < y ? x : y; }
namespace Poly {
	const int mod = 998244353;
	inline int add(int x, int y) { return x + y < mod ? x + y : x + y - mod; }
	inline int sub(int x, int y) { return x - y < 0 ? x - y + mod : x - y; }
	inline int mul(int x, int y) { return (int)((ll)x * y % mod); }
	inline int Get(int x) { int ss = 1; for(; ss <= x; ss <<= 1); return ss; }
	inline int ksm(int x, int y = mod - 2) {
		int ss = 1; for(; y; y >>= 1, x = mul(x, x)) if(y & 1) ss = mul(ss, x);
		return ss;
	}
	void ntt(vector<int> &A, int lmt, int opt) {
		A.resize(lmt + 5);
		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 R = mid << 1, j = 0; j < lmt; j += R)
				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 i = 0, inv = ksm(lmt); i < lmt; i++) A[i] = mul(A[i], inv);
	}
	vector<int> Add(const vector<int> &a, const vector<int> &b) {
		vector<int> res(Max(a.size(), b.size()));
		for(int i = 0; i < res.size(); i++) {
			if(i < a.size()) res[i] = add(res[i], a[i]);
			if(i < b.size()) res[i] = add(res[i], b[i]);
		}
		return res;
	}
	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;
	}
	vector<int> Inv(const vector<int> &A, int sz = -1) {
		if(sz == -1) sz = A.size();
		vector<int> res; if(sz == 1) return res.pb(ksm(A[0])), res;
		res = Inv(A, (sz + 1) / 2);
		vector<int> tmp(A.begin(), A.begin() + sz);
		int lmt = Get(sz * 2 - 2);
		ntt(tmp, lmt, 1), ntt(res, lmt, 1);
		for(int i = 0; i < lmt; i++)
			res[i] = mul(sub(2, mul(res[i], tmp[i])), res[i]);
		ntt(res, lmt, -1); return res.resize(sz), res;
	}
	vector<int> Sqrt(const vector<int> &A, int sz = -1) {
		if(sz == -1) sz = A.size();
		vector<int> res; if(sz == 1) return res.pb(1), res;
		res = Sqrt(A, (sz + 1) / 2);
		vector<int> tmp(A.begin(), A.begin() + sz);
		res.resize(sz), res = Add(res, Mul(tmp, Inv(res)));
		for(int i = 0; i < res.size(); i++)
			res[i] = (res[i] & 1) ? ((res[i] + mod) / 2) : (res[i] / 2);
		return res.resize(sz), res;
	}
	void Div(const vector<int> &A, const vector<int> &B, vector<int> &D, vector<int> &R) {
		if(B.size() > A.size()) return (void)(D.clear(), D.pb(0), R = A);
		vector<int> a = A, b = B, iB; int n = A.size(), m = B.size();
		reverse(a.begin(), a.end()), reverse(b.begin(), b.end());
		b.resize(n - m + 1), iB = Inv(b, n - m + 1);
		D = Mul(a, iB), D.resize(n - m + 1), reverse(D.begin(), D.end());
		R = Mul(B, D);
		for(int i = 0; i < m - 1; i++) R[i] = (mod + A[i] - R[i]) % mod;
		R.resize(m - 1);
	}
	vector<int> Ln(const vector<int> &A) {
		vector<int> f, g = Inv(A); f.resize(A.size());
		for(int i = 1; i < f.size(); i++) f[i - 1] = mul(i, A[i]);
		f[f.size() - 1] = 0, f = Mul(f, g), f.resize(A.size());
		for(int i = f.size() - 1; i > 0; i--) f[i] = mul(f[i - 1], ksm(i));
		f[0] = 0; return f;
	}
	vector<int> Exp(const vector<int> &A, int sz = -1) {
		if(sz == -1) sz = A.size();
		vector<int> res; if(sz == 1) return res.pb(1), res;
		res = Exp(A, (sz + 1) / 2), res.resize(sz); vector<int> tmp = Ln(res);
		for(int i = 0; i < tmp.size(); i++) tmp[i] = add(sub(0, tmp[i]), A[i]);
		tmp[0] = add(1, tmp[0]), res = Mul(res, tmp);
		return res.resize(sz), res;
	}
	vector<int> Ksm(const vector<int> &A, const vector<int> &K) {
		vector<int> res = Ln(A); int k = 0;
		for(int i = 0; i < K.size(); i++) k = add(mul(k, 10), K[i]);
		for(int i = 0; i < res.size(); i++) res[i]= mul(res[i], k);
		res = Exp(res), res.resize(A.size()); return res;
	}
}
const int N = 200010;
int n, m;
char s[N];
vector<int> a, b;
int main() {
	scanf("%d%s", &n, &s);
	for(int i = 0, ed = strlen(s); i < ed; i++) b.pb(s[i] - '0');
	for(int i = 0, x; i < n; i++) scanf("%d", &x), a.pb(x);
	a = Poly::Ksm(a, b);
	for(int i = 0; i < n; i++) printf("%d ", a[i]); puts("");
	return 0;
}