[C++知识库]【luogu P5273】【模板】多项式幂函数（加强版）（NTT）

【模板】多项式幂函数（加强版）

题目链接：luogu P5273

题目大意

给你一个 n-1 次多项式，要你求它的 k 次方模 x^n 意义下结果。
不保证给出多项式常数项为 1。

思路

我们考虑常数项不是一会怎样。

$A^k(x)=e^{\ln (A(x))?k}$
会发现问题出在 $\ln (A(x))$ 需要常数项是 $1$。

那不是 $1$ 咋办？
考虑先除常数项，然后正常算，然后常数项的 $k$ 次方算出来，然后再乘回去。
（然后这里要注意一下常数项 $k$ 次方这里的 $k$ 是 $\%(998244353?1)$ 的【欧拉定理】）

然后就可以了？其实会挂，因为常数项可能是 $0$。
那咋办呢？那就直接找第一个不是 $0$ 的项，先左移，算出来再右移。

然后你要注意看一下前面 $0$ 的数量会不会超过 $n?1$ 次，如果超了就肯定是全 $0$。
（这里记得你的 $k$ 取模了，所以你如果要用取模后的 $k$ 你要判断一下 $k$ 字符串的长度是否明显大于 $n$）

然后就可以了。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#define mo 998244353
#define clr(f, n) memset(f, 0, (n) * sizeof(int))
#define cpy(f, g, n) memcpy(f, g, (n) * sizeof(int))

using namespace std;

const int N = 100000 * 8 + 1;
int n, m, f[N], g[N], an[N], inv[N], G, Gv;
int Gs[N], Gvs[N], Ws[N];
char s[100001];

int jia(int x, int y) {return x + y >= mo ? x + y - mo : x + y;}
int jian(int x, int y) {return x - y < 0 ? x - y + mo : x - y;}
int cheng(int x, int y) {return 1ll * x * y % mo;}
int ksm(int x, int y) {int re = 1; while (y) {if (y & 1) re = cheng(re, x); x = cheng(x, x); y >>= 1;} return re;}

void Init() {
	G = 3; Gv = ksm(G, mo - 2);
	inv[0] = inv[1] = 1; for (int i = 2; i < N; i++) inv[i] = cheng(inv[mo % i], mo - mo / i);
	for (int i = 1; i < N; i <<= 1) {
		Gs[i] = ksm(G, (mo - 1) / (i << 1));
		Gvs[i] = ksm(Gv, (mo - 1) / (i << 1));
	}
}

void get_an(int limit, int l_size) {
	for (int i = 0; i < limit; i++)
		an[i] = (an[i >> 1] >> 1) | ((i & 1) << (l_size - 1)); 
}

void NTT(int *f, int limit, int op) {
	for (int i = 0; i < limit; i++) if (an[i] < i) swap(f[an[i]], f[i]);
	for (int mid = 1; mid < limit; mid <<= 1) {
		//int Wn = ksm(op == 1 ? G : Gv, (mo - 1) / (mid << 1));
		int Wn = (op == 1) ? Gs[mid] : Gvs[mid];
		Ws[0] = 1; for (int i = 1; i < mid; i++) Ws[i] = cheng(Ws[i - 1], Wn);
		for (int R = (mid << 1), j = 0; j < limit; j += R) {
//			int w = 1;
//			for (int k = 0; k < mid; k++, w = cheng(w, Wn)) {
			for (int k = 0; k < mid; k++) {
//				int x = f[j | k], y = cheng(w, f[j | mid | k]);
				int x = f[j | k], y = cheng(Ws[k], f[j | mid | k]);
				f[j | k] = jia(x, y); f[j | mid | k] = jian(x, y);
			}
		}
	}
	if (op == -1) {
		int limv = ksm(limit, mo - 2);
		for (int i = 0; i < limit; i++) f[i] = cheng(f[i], limv);
	}
}

void px(int *f, int *g, int limit) {
	for (int i = 0; i < limit; i++)
		f[i] = cheng(f[i], g[i]);
}

void times(int *f, int *g, int n, int m) {
	static int tmp[N];
	int limit = 1, l_size = 0; while (limit < n + n) limit <<= 1, l_size++;
	cpy(tmp, g, n); clr(tmp + n, limit - n);
	get_an(limit, l_size);
	NTT(f, limit, 1); NTT(tmp, limit, 1);
	px(f, tmp, limit); NTT(f, limit, -1);
	clr(f + m, limit - m); clr(tmp, limit);
}

void invp(int *f, int n) {
	static int w[N], r[N], tmp[N];
	w[0] = ksm(f[0], mo - 2);
	int limit = 1, l_size = 0;
	for (int len = 2; (len >> 1) <= n; len <<= 1) {
		limit = len; l_size++; get_an(limit, l_size);
		cpy(r, w, len >> 1);
		cpy(tmp, f, limit); NTT(tmp, limit, 1);
		NTT(r, limit, 1); px(r, tmp, limit);
		NTT(r, limit, -1); clr(r, limit >> 1);
		cpy(tmp, w, len); NTT(tmp, limit, 1);
		NTT(r, limit, 1); px(r, tmp, limit);
		NTT(r, limit, -1);
		for (int i = (len >> 1); i < len; i++)
			w[i] = jian(cheng(w[i], 2), r[i]);
	}
	cpy(f, w, n); clr(w, limit); clr(r, limit); clr(tmp, limit);
}

void dao(int *f, int n) {
	for (int i = 1; i < n; i++)
		f[i - 1] = cheng(f[i], i);
	f[n - 1] = 0;
}

void jifen(int *f, int n) {
	for (int i = n; i >= 1; i--)
		f[i] = cheng(f[i - 1], inv[i]);
	f[0] = 0;
}

void mof(int *f, int n, int *g, int m) {
	static int f_[N], g_[N];
	int L = n - m + 1;
	reverse(f, f + n); cpy(f_, f, L); reverse(f, f + n); 
	reverse(g, g + m); cpy(g_ , g, L); reverse(g, g + m);
	invp(g_, L); times(g_, f_, L, L); reverse(g_, g_ + L);
	
	times(g, g_, n, n);
	for (int i = 0; i < m - 1; i++) g[i] = jian(f[i], g[i]);
	clr(g + m - 1, L);
	cpy(f, g_, L); clr(f + L, n - L);
}

void lnp(int *f, int n) {
	static int g[N];
	cpy(g, f, n); dao(g, n);
	invp(f, n); times(f, g, n, n);
	jifen(f, n - 1); clr(g, n);
}

void exp(int *f, int n) {
	static int w[N], ww[N];
	ww[0] = 1;
	int len;
	for (len = 2; (len >> 1) <= n; len <<= 1) {
		cpy(w, ww, len >> 1); lnp(w, len);
		for (int i = 0; i < len; i++)
			w[i] = jian(f[i], w[i]);
		w[0] = jia(w[0], 1);
		times(ww, w, len, len);
	}
	len >>= 1;
	cpy(f, ww, n); clr(ww, len); clr(w, len);
}

void ksmp(int *f, int n, int k) {
	lnp(f, n);
	for (int i = 0; i < n; i++) f[i] = cheng(f[i], k);
	exp(f, n);
}

void ksmp_ex(int *f, int n, int k, int kk) {
	int di = 0, c;
	while (!f[di]) di++; c = ksm(f[di], mo - 2);
	if (di && (strlen(s + 1) > 5 || 1ll * di * k >= n)) {
		clr(f, n); return ;
	}
	n -= di * k;
	for (int i = 0; i < n; i++) f[i] = cheng(f[i + di], c);
	clr(f + n, di * k); ksmp(f, n, k);
	c = ksm(c, mo - 2); c = ksm(c, kk);
	static int g[N];
	for (int i = 0; i < n; i++) g[di * k + i] = cheng(f[i], c);
	cpy(f, g, di * k + n); clr(g, di * k + n);
}

int main() {
	Init();
	
	scanf("%d %s", &n, s + 1);
	for (int i = 0; i < n; i++) scanf("%d", &f[i]);
	
	int k = 0, kk = 0, sn = strlen(s + 1);
	for (int i = 1; i <= sn; i++) k = jia(cheng(k, 10), s[i] - '0');
	for (int i = 1; i <= sn; i++) kk = (1ll * kk * 10 + s[i] - '0') % (mo - 1);
	
	ksmp_ex(f, n, k, kk);
	
	for (int i = 0; i < n; i++) printf("%d ", f[i]);
	
	return 0;
}