【模板】快速数论变换

标签：ch 数论 lim rev long 变换 int 模板 mod

依旧是常数很大的板子。

在 H_Kaguya 改动之前，达到了 \(2.61\,s\) 的绝望时间

现在好多了，\(1.10\,s\)。（内存不连续访问我会记你一辈子的）

#include <iostream>
char ch;
short get_single() {
	ch = getchar();
	while(ch < '0') 
		ch = getchar();
	return ch&15;
}
const int mod = 998244353;
const int g = 3;
const int g_inv = 332748118;
const int N = 2100010;
long long quick_pow(long long _a,int _n,int _p = mod) {
	long long _res = 1;
	while(_n) {
		if(_n&1) 
			_res = _res*_a%_p;
		_a = _a*_a%_p;
		_n >>= 1;
	}
	return _res;
}
int rev[N];
int a[N], b[N];
int lim;
void ntt_init() {
	int tmp = lim>>1;
	for(int i = 1;i < lim;++i) {
		rev[i] = rev[i>>1]>>1;
		if(i&1) 
			rev[i] |= tmp;
	}
}
void NTT(int *f,int opt) {
	for(int i = 0;i < lim;++i) 
		if(i < rev[i]) 
			std :: swap(f[i],f[rev[i]]);
	long long w_n, w;
	for(register int i = 1, step = 2;i < lim;i <<= 1, step <<= 1) {
		w_n = quick_pow(~opt ? g : g_inv,(mod-1)/step);
		for(register int j = 0, upd = i;j < lim;j += step, upd += step) {
			w = 1;
			for(register int k = j, l = i+j;k < upd;++k, ++l, w = w*w_n%mod) {
				int y = w*f[l]%mod;
				f[l] = f[k]-y;
				if(f[l] < 0) 
					f[l] += mod;
				f[k] += y;
				if(f[k] >= mod) 
					f[k] -= mod;
			}
		}
	}
	if(!~opt) {
		long long inv_lim = quick_pow(lim,mod-2);
		for(int i = 0;i < lim;++i) 
			f[i] = f[i]*inv_lim%mod;
	}
}
int n, m;
int main() {
	scanf("%d %d",&n,&m);
	for(int i = 0;i <= n;++i) 
		a[i] = get_single();
	for(int i = 0;i <= m;++i) 
		b[i] = get_single();
	n += m;
	lim = 1<<31-__builtin_clz(n);
	if(lim&n) 
		lim <<= 1;
	ntt_init();
	NTT(a,1);
	NTT(b,1);
	for(int i = 0;i < lim;++i) 
		a[i] = 1ll*a[i]*b[i]%mod;
	NTT(a,-1);
	for(int i = 0;i <= n;++i) 
		printf("%d ",a[i]);
	return 0;
}

标签：ch,数论,lim,rev,long,变换,int,模板,mod
From： https://www.cnblogs.com/bikuhiku/p/Fast_Number-Theoretic_Transform.html