임의의 모드 NTT

삼 모드 NTT
할 줄 모르다
원래 3 모드 NTT 를 쓰 려 고 했 는데 상수 가 너무 큰 것 을 발 견 했 습 니 다. 어떻게 최적화 해 야 할 지 모 르 겠 으 니 해체 계수 FFT 를 쓰 세 요.
먼저 간단 한 방법 은 바로 FFT 에서 long double 을 운전 하여 달 리 는 것 이다. 정밀도 가 매우 심각하게 떨 어 진 것 을 발견 하고 (당직 구역 이 long long 보다 크다) 어떻게 해결 할 것 인 가 를 고려 하 는 것 이다.
bitset 를 배 운 경험 을 통 해 우 리 는 자 리 를 낮 춰 야 한 다 는 것 을 알 고 있다.
해체 계수 고려
다항식 A ∗ B 를 가정 하면 모 수 는 P A * B 이 고 모 수 는 P A ∗ B 이 며 모 수 는 P 이다.
상수 C 를 확인 하려 면 보통 2 15 = 32, 768 또는 P 로 상수 C 를 확인 하 십시오. 보통 2 ^ {15} = 32, 768 또는 \ sqrt {P} 상수 C 를 확인 하려 면 보통 215 = 32, 768 또는 P 입 니 다.
A i 를 a i * 8727 ° C + b i 로 뜯 는 것 을 고려 하여 Ai 분해 ai *C+b_i. Ai 를 ai * 8727 ° C + bi 로 뜯 고 B i 를 c * 8727 ° C + d 로 뜯 고 Bi 분해 ci *C+d_i. Bi 를 ci ∗ C + di 즉 A i = a i ∗ C + b i A 로 뜯 어 낸다.i = a_i *C+b_i Ai​=ai​∗C+bi​ B i = c i ∗ C + d i B_i = c_i *C+d_i Bi = ci ∗ C + di 는 두 개의 수 X, Y X, Y X, Y 곱 하기 를 고려한다
설정 X = a ∗ C + b 설정 X = a * C + b 설정 X = a * C + b 설정 X = a * C + b Y = c ∗ C + d Y = c * C + d Y = c * C + d Y = c ∗ C + d X ∗ Y = (a \8727C + b) ∗ (c \8727C + d) X * Y = (a * C + b) X * Y = (a * C + b) * C + b) * (c * C + b) * (c * C + d) * C + d) X * C + d) X \8727Y = (a * C + b) \8727C + b) ∗ (c + C + d) C + d) X * C + b) * (c * C + b) = a c ∗ C 2 + (a d + b c) C + b d = ac * C ^ 2 + (ad + bc) C + bd = ac ∗ C2 + (ad + bc) C + bd 발견 C 는 상관 하지 않 고 a c, a d + b c, b d ac, ad + bc, bd ac, ad + bc,bd 다음 에 a, b, c, d a, b, c, d a, b, c, d 를 각각 값 (DFT) 을 구하 고 곱 한 다음 에 a c, a d + b c, b d ac, ad + bc, bd ac, ad + bc, bd 를 삽입 값 (IDFT) 으로 하면 됩 니 다. 모두 4 번 DFT + 3 번 IDFT = 7 번 FFT 상수 가 큽 니 다.
처음에는 허수 부가 사용 되 지 않 았 음 을 발 견 했 습 니 다. FFT 3 차 변 2 차 의 최적화 를 참고 하여 이것 이 가능 한 지 시험 해 보 세 요.
설정 X = a + b i 설정 X = a + bi 설정 X = a + bi Y = c + d i Y = c + di Y = c + di
X ∗ Y = ( a + b i ) ∗ ( c + d i ) = a c − b d + ( b c + a d ) i X*Y=(a+bi)*(c+di)=ac-bd + (bc+ad)i X∗Y=(a+bi)∗(c+di)=ac−bd+(bc+ad)i
거위 와 우리 가 요구 하 는 a c, b d, a d + b c ac, bd, ad + bc ac, bd, ad + bc 는 현재 a d + b c ad + bc ad + bc 가 나 왔 습 니 다.
어떻게 두 개 를 구 할 것 인 가 를 고려 하 다.
설정 X ′ = a − b i 설정 X '= a - bi 설정 X ′ = a - bi 설정 X ′ = a − bi Y = c + d i Y = c + di Y = c + di X ′ ′ ∗ Y = (a − b i) ∗ (c + d i) = a c + b d + (a d − b c) i X' * Y = (a - bi) * (c + di) * (c + (c + di) = ac + bd + (ad - bd + (ad - bc) i X ′ (ad - bc) i X ′ ∗ Y = (a - bi) ∗ (c + di) = ac + bd + bd + (ad - bd + (ad - bc) i) i X ′ Y = (a - bc) i
그리고 실수 부 를 알 게 되 었 고 실수 부 를 알 게 되 었 습 니 다. 그리고 실수 부 ac + bd 의 값 의 값 을 알 게 되 었 습 니 다. 위의 a c - b d 의 값 을 결합 하면 a c 와 b d 를 구 할 수 있 습 니 다. 위의 ac - bd 의 값 을 결합 하면 ac - bd 의 값 을 구 할 수 있 습 니 다. 이렇게 하면 X, Y 만 사용 하 는 것 같 습 니 다.X ′ 이러 면 X, Y, X '이러 면 X, Y, X ′ 에 만 3 번 값 구하 기 (DFT) 하고 X ∗ Y, X ′ ∗ Y 에 X * Y, X' * Y 에 X ∗ Y, X ′ ∗ Y 에 두 번 삽입 하면 돼.
그 러 니까 총 5 번.
my y 는 4 번 의%%%%% orz 가 있다 고 합 니 다.
code:

#include
#define N 4000005
#define ll long long
#define double long double
using namespace std;
const double pi = acos(-1);
const double eps = 0.49;
const int C = 32768;
struct cp {
	double a, b;
}X[N], Y[N], Xd[N];
cp operator +(cp x, cp y) {return cp{x.a + y.a, x.b + y.b};}
cp operator -(cp x, cp y) {return cp{x.a - y.a, x.b - y.b};}
cp operator *(cp x, cp y) {return cp{x.a * y.a - x.b * y.b, x.b * y.a + x.a * y.b};}
int rev[N], n, m, P;
void fft(cp *a, int len, int o) {
	for(int i = 1; i <= len; i ++) rev[i] = (rev[i >> 1] >> 1) | ((i&1) * len >> 1);
	for(int i = 1; i <= len; i ++) if(i < rev[i]) swap(a[i], a[rev[i]]);

	for(int i = 2; i <= len; i <<= 1) {
		cp wn = cp{cos(2 * pi / i), o * sin(2 * pi / i)};
		for(int j = 0, p = i / 2; j + i - 1 <= len; j += i) {
			cp w0 = cp{1, 0};
			for(int k = j; k < j + p; k ++, w0 = w0 * wn) {
				cp x = a[k], y =  w0 * a[k + p];
				a[k] = x + y;
				a[k + p] = x - y;
			}
		}
	}
	if(o == -1) for(int i = 0; i <= len; i ++) a[i].a /= len, a[i].b /= len;
}
int main() {
	scanf("%d%d%d", &n, &m, &P);
	for(int i = 0; i <= n; i ++) {
		int x;
		scanf("%d", &x);
		X[i].a = x / C;
		X[i].b = x % C;
		Xd[i].a = x / C;
		Xd[i].b = -(x % C);
	}
	for(int i = 0; i <= m; i ++) {
		int x;
		scanf("%d", &x);
		Y[i].a = x / C;
		Y[i].b = x % C;
	}
	int len = 1;
	for(; len <= n + m;) len <<= 1;
	fft(X, len, 1), fft(Xd, len, 1), fft(Y, len, 1);
	for(int i = 0; i <= len; i ++) X[i] = X[i] * Y[i], Xd[i] = Xd[i] * Y[i];
	fft(X, len, -1), fft(Xd, len, -1);
	for(int i = 0; i <= n + m; i ++) {
		ll ac = (X[i].a + Xd[i].a) / 2 + eps;
		ll bd = Xd[i].a - ac + eps;
		ll bcad = X[i].b + eps;
		printf("%lld ", (ac * C % P * C % P + bcad * C % P + bd) % P);
	}
	return 0;
}

감동
임 의 모드 다항식 구 역
code:

#include
#define N 4000005
#define ll long long
#define double long double
using namespace std;
const double pi = acos(-1);
const double eps = 0.49;
const int C = 32768;
struct cp {
	double a, b;
}X[N], Y[N], Xd[N];
cp operator +(cp x, cp y) {return cp{x.a + y.a, x.b + y.b};}
cp operator -(cp x, cp y) {return cp{x.a - y.a, x.b - y.b};}
cp operator *(cp x, cp y) {return cp{x.a * y.a - x.b * y.b, x.b * y.a + x.a * y.b};}
int rev[N], P;
void fft(cp *a, int len, int o) {
	for(int i = 1; i <= len; i ++) rev[i] = (rev[i >> 1] >> 1) | ((i&1) * len >> 1);
	for(int i = 1; i <= len; i ++) if(i < rev[i]) swap(a[i], a[rev[i]]);

	for(int i = 2; i <= len; i <<= 1) {
		cp wn = cp{cos(2 * pi / i), o * sin(2 * pi / i)};
		for(int j = 0, p = i / 2; j + i - 1 <= len; j += i) {
			cp w0 = cp{1, 0};
			for(int k = j; k < j + p; k ++, w0 = w0 * wn) {
				cp x = a[k], y =  w0 * a[k + p];
				a[k] = x + y;
				a[k + p] = x - y;
			}
		}
	}
	if(o == -1) for(int i = 0; i <= len; i ++) a[i].a /= len, a[i].b /= len;
}
void mul(ll *a, ll *b, int n, int m) {
	for(int i = 0; i <= n; i ++) {
		X[i].a = a[i] / C;
		X[i].b = a[i] % C;
		Xd[i].a = a[i] / C;
		Xd[i].b = -(a[i] % C);
	}
	for(int i = 0; i <= m; i ++) {
		Y[i].a = b[i] / C;
		Y[i].b = b[i] % C;
	}
	int len = 1;
	for(; len <= n + m;) len <<= 1;
	fft(X, len, 1), fft(Xd, len, 1), fft(Y, len, 1);
	for(int i = 0; i <= len; i ++) X[i] = X[i] * Y[i], Xd[i] = Xd[i] * Y[i];
	fft(X, len, -1), fft(Xd, len, -1);
	for(int i = 0; i <= n + m; i ++) {
		ll ac = (X[i].a + Xd[i].a) / 2 + eps;
		ll bd = Xd[i].a - ac + eps;
		ll bcad = X[i].b + eps;
		a[i] = (ac % P * C % P * C % P + bcad % P * C % P + bd % P) % P;
	}
	for(int i = 0; i <= len; i ++) X[i].a = X[i].b = Y[i].a = Y[i].b = Xd[i].a = Xd[i].b = 0;
}
int qpow(ll x, int y) {
	ll ret = 1;
	for(; y; y >>= 1, x = x * x % P) if(y & 1) ret = ret * x % P;
	return ret;
}
ll c[N], d[N], e[N], n;
void inv(ll *a, ll *b, int sz){
	if(sz == 0) {b[0] = qpow(a[0], P - 2); return;}
	inv(a, b, sz / 2);
	int len = 1;
	for(; len <= sz + sz; len <<= 1);
	for(int i = 0; i <= sz; i ++) c[i] = a[i];
	for(int i = sz + 1; i <= len; i ++) c[i] = 0;
	
	//for(int i = 0; i <= len; i ++) b[i] = (b[i] * 2 % mod - b[i] * b[i] % mod * c[i] % mod + mod) % mod;//Ö±½ÓËã
	
	for(int i = 0; i <= sz; i ++) e[i] = b[i] * 2 % P;
	for(int i = sz + 1; i <= len; i ++) e[i] = 0;
	
	for(int i = 0; i <= sz; i ++) d[i] = b[i]; 
	for(int i = sz + 1; i <= len; i ++) d[i] = 0;
	
	mul(b, d, sz, sz); mul(b, c, sz, sz);
	for(int i = 0; i <= sz; i ++) b[i] = (e[i] - b[i] + P) % P;
	
	for(int i = sz + 1; i <= len; i ++) b[i] = 0;
	
}
ll a[N], b[N];
int main() {
	scanf("%d", &n);
	n --;
	P = 1000000007;
	for(int i = 0; i <= n; i ++) scanf("%lld", &a[i]);
	inv(a, b, n);
	for(int i = 0; i <= n; i ++) printf("%lld ", b[i]);
	return 0;
}