제출 #1261162

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1261162		kaiboy	Multiply (CEOI17_mul)	C++20	100 / 100	16 ms	1608 KiB

mul

#include <algorithm>
#include <iostream>

using namespace std;

const int  N = 50000;
const int  L = 17;
const int N_ = 1 << L;
const int MD = 998244353;

char cc[N * 2 + 2];
int aa[N_], bb[N_];

long long power(long long a, int k) {
	long long p = 1;
	for ( ; k; k >>= 1) {
		if (k & 1)
			p = p * a % MD;
		a = a * a % MD;
	}
	return p;
}

void ntt(int *aa, int l, bool inverse) {
	int n = 1 << l;
	for (int i = 0, j = 1; j < n; j++) {
		for (int b = n >> 1; !((i ^= b) & b); b >>= 1)
			;
		if (i < j)
			swap(aa[i], aa[j]);
	}
	for (int h = 0; h < l; h++) {
		int m = 1 << h, w = power(3, MD - 1 >> h + 1);
		if (inverse)
			w = power(w, MD - 2);
		long long w_ = 1;
		for (int r = 0; r < m; r++) {
			for (int i = r, j; i < n; i += m << 1) {
				int a = aa[i], b = aa[j = i + m] * w_ % MD;
				if ((aa[i] = a + b) >= MD)
					aa[i] -= MD;
				if ((aa[j] = a - b) < 0)
					aa[j] += MD;
			}
			w_ = w_ * w % MD;
		}
	}
}

void convolute(int *aa, int *bb, int l) {
	int n = 1 << l;
	ntt(aa, l, false);
	ntt(bb, l, false);
	for (int i = 0; i < n; i++)
		aa[i] = (long long) aa[i] * bb[i] % MD;
	ntt(aa, l, true);
	long long v = power(n, MD - 2);
	for (int i = 0; i < n; i++)
		aa[i] = aa[i] * v % MD;
}

int main() {
	int n, m; cin >> n >> m;
	int l = 0, n_ = 1;
	while (n_ < n + m + 1)
		l++, n_ <<= 1;
	cin >> cc;
	for (int i = 0; i < n; i++)
		aa[i] = cc[n - 1 - i] - '0';
	cin >> cc;
	for (int i = 0; i < m; i++)
		bb[i] = cc[m - 1 - i] - '0';
	convolute(aa, bb, l);
	for (int i = 0; i + 1 < n_; i++)
		aa[i + 1] += aa[i] / 10, aa[i] %= 10;
	while (n_ > 1 && !aa[n_ - 1])
		n_--;
	for (int i = 0; i < n_; i++)
		cc[i] = aa[n_ - 1 - i] + '0';
	cc[n_] = '\0';
	cout << cc << '\n';
	return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30