\(\text{FFT}\)

#include <cstdio>

#include <cmath>

#include <iostream>

#include <cstring>

#define re register

using namespace std;

const int N = 2e6 + 1e5;

int c[N], rev[N];

char s[N];

const double Pi = acos(-1.0);

struct complex{

	double x, y;

	inline complex(double xx = 0, double yy = 0){x = xx, y = yy;}

	inline complex operator + (const complex &b) const {return complex(x + b.x, y + b.y);}

	inline complex operator - (const complex &b) const {return complex(x - b.x, y - b.y);}

	inline complex operator * (const complex &b) const {return complex(x * b.x - y * b.y, x * b.y + y * b.x);}

}a[N], b[N];

inline void FFT(complex *a, int lim, int inv)

{

	for(re int i = 0; i < lim; i++)

	if (i < rev[i]) swap(a[i], a[rev[i]]);

	for(re int mid = 1; mid < lim; mid <<= 1)

	{

		complex I = complex(cos(Pi / mid), inv * sin(Pi / mid));

		for(re int i = 0; i < lim; i += mid << 1)

		{

			complex W = complex(1, 0);

			for(re int j = 0; j < mid; j++, W = W * I)

			{

				complex x = a[i + j], y = W * a[i + j + mid];

				a[i + j] = x + y, a[i + j + mid] = x - y;

			}

		}

	}

}

int main()

{

	scanf("%s", s);

	int n = strlen(s);

	for(re int i = 0; i < n; i++) a[i].x = s[n - i - 1] ^ 48;

	scanf("%s", s);

	int m = strlen(s);

	for(re int i = 0; i < m; i++) b[i].x = s[m - i - 1] ^ 48;

	int limit = 1;

	while (limit < n + m - 1) limit <<= 1;

	int bit = 0;

	while ((1 << bit) < limit) ++bit;

	for(re int i = 0; i < limit; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));

	FFT(a, limit, 1), FFT(b, limit, 1);

	for(re int i = 0; i < limit; i++) a[i] = a[i] * b[i];

	FFT(a, limit, -1);

	for(re int i = 0; i < limit; i++) c[i] = int(a[i].x / limit + 0.5);

	for(re int i = 0; i < limit; i++)

	{

		if (c[i] >= 10) c[i + 1] += c[i] / 10, limit = ((i + 1) == limit ? limit + 1 : limit);

		c[i] %= 10;

	}

	while (limit && !c[limit]) --limit;

	for(re int i = limit; i >= 0; i--) printf("%d", c[i]);

}

\(\text{NTT}\)

#include <cstdio>

#include <iostream>

#include <cstring>

#define re register

using namespace std;

const int N = 2e6 + 1e5;

const int P = 998244353, g = 3;

int a[N], b[N], rev[N];

char s[N];

inline int fpow(int x, int y)

{

	int res = 1;

	for(; y; y >>= 1)

	{

		if (y & 1) res = 1LL * res * x % P;

		x = 1LL * x * x % P;

	}

	return res;

}

inline void NTT(int *a, int lim, int inv)

{

	if (lim == 1) return;

	for(re int i = 0; i < lim; i++)

	if (i < rev[i]) swap(a[i], a[rev[i]]);

	for(re int mid = 1, I; mid < lim; mid <<= 1)

	{

		I = fpow(g, (P - 1) / (mid << 1));

		if (inv == -1) I = fpow(I, P - 2);

		for(re int i = 0, W; i < lim; i += mid << 1)

		{

			W = 1;

			for(re int j = 0, x, y; j < mid; j++, W = 1LL * W * I % P)

			{

				x = a[i + j], y = 1LL * W * a[i + j + mid] % P;

				a[i + j] = (x + y) % P, a[i + j + mid] = (x - y + P) % P;

			}

		}

	}

}

int main()

{

	scanf("%s", s);

	int n = strlen(s);

	for(re int i = 0; i < n; i++) a[i] = s[n - i - 1] ^ 48;

	scanf("%s", s);

	int m = strlen(s);

	for(re int i = 0; i < m; i++) b[i] = s[m - i - 1] ^ 48;

	int limit = 1;

	while (limit < n + m - 1) limit <<= 1;

	int bit = 0;

	while ((1 << bit) < limit) ++bit;

	for(re int i = 0; i < limit; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));

	NTT(a, limit, 1), NTT(b, limit, 1);

	for(re int i = 0; i < limit; i++) a[i] = 1LL * a[i] * b[i] % P;

	NTT(a, limit, -1);

	int inv = fpow(limit, P - 2);

	for(re int i = 0; i < limit; i++) a[i] = 1LL * a[i] * inv % P;

	for(re int i = 0; i < limit; i++)

	{

		if (a[i] >= 10) a[i + 1] += a[i] / 10, limit = ((i + 1) == limit ? limit + 1 : limit);

		a[i] %= 10;

	}

	while (limit && !a[limit]) --limit;

	for(re int i = limit; i >= 0; i--) printf("%d", a[i]);

}

巴特西

LG P1919

\(\text{FFT}\)

\(\text{NTT}\)

最新文章

热门文章