Submission #741218

#	Time	Username	Problem	Language	Result	Execution time	Memory
741218		rainboy	Multiply (CEOI17_mul)	C11	100 / 100	31 ms	2892 KiB

mul

#include <stdio.h>
#include <stdlib.h>

#define N	50000
#define M	50000
#define L	17	/* L = ceil(log2(N + M)) */
#define N_	(1 << L)
#define MD	998244353

long long power(long long a, int k) {
	long long p = 1;

	while (k) {
		if (k & 1)
			p = p * a % MD;
		a = a * a % MD;
		k >>= 1;
	}
	return p;
}

int *wwu[L + 1], *wwv[L + 1], vv_[L + 1];

void init() {
	int l, u, v;

	u = power(3, MD - 1 >> L), v = power(u, MD - 2);
	for (l = L; l > 0; l--) {
		int n = 1 << l, m = n >> 1, i;

		vv_[l] = power(n, MD - 2);
		wwu[l] = (int *) malloc(m * sizeof *wwu[l]);
		wwv[l] = (int *) malloc(m * sizeof *wwv[l]);
		wwu[l][0] = wwv[l][0] = 1;
		for (i = 1; i < m; i++) {
			wwu[l][i] = (long long) wwu[l][i - 1] * u % MD;
			wwv[l][i] = (long long) wwv[l][i - 1] * v % MD;
		}
		u = (long long) u * u % MD, v = (long long) v * v % MD;
	}
	vv_[0] = 1;
}

void ntt_(int *aa, int l, int inverse) {
	if (l) {
		int n = 1 << l, m = n >> 1, *ww = inverse ? wwv[l] : wwu[l], i, j;

		ntt_(aa, l - 1, inverse), ntt_(aa + m, l - 1, inverse);
		for (i = 0; (j = i + m) < n; i++) {
			int a = aa[i], b = (long long) aa[j] * ww[i] % MD;

			if ((aa[i] = a + b) >= MD)
				aa[i] -= MD;
			if ((aa[j] = a - b) < 0)
				aa[j] += MD;
		}
	}
}

void ntt(int *aa, int l, int inverse) {
	int n = 1 << l, i, j;

	for (i = 0, j = 1; j < n; j++) {
		int m = n >> 1, tmp;

		while ((i ^= m) < m)
			m >>= 1;
		if (i < j)
			tmp = aa[i], aa[i] = aa[j], aa[j] = tmp;
	}
	ntt_(aa, l, inverse);
}

int main() {
	static char aa[N + 1], bb[M + 1];
	static int aa_[N_], bb_[N_], cc[N + M];
	int n, m, n_, l_, i, j;

	init();
	scanf("%d%d%s%s", &n, &m, aa, bb);
	for (i = 0; i < n; i++)
		aa_[i] = aa[n - 1 - i] - '0';
	for (j = 0; j < m; j++)
		bb_[j] = bb[m - 1 - j] - '0';
	l_ = 0;
	while (1 << l_ < n + m)
		l_++;
	n_ = 1 << l_;
	ntt(aa_, l_, 0), ntt(bb_, l_, 0);
	for (i = 0; i < n_; i++)
		aa_[i] = (long long) aa_[i] * bb_[i] % MD;
	ntt(aa_, l_, 1);
	for (i = 0; i < n_; i++)
		aa_[i] = (long long) aa_[i] * vv_[l_] % MD;
	for (i = 0; i + 1 < n + m; i++) {
		cc[i] += aa_[i];
		cc[i + 1] += cc[i] / 10, cc[i] %= 10;
	}
	i = n + m - 1;
	while (i > 0 && cc[i] == 0)
		i--;
	while (i >= 0)
		printf("%d", cc[i--]);
	printf("\n");
	return 0;
}

Compilation message (stderr)

mul.c: In function 'init':
mul.c:27:22: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   27 |  u = power(3, MD - 1 >> L), v = power(u, MD - 2);
      |                      ^~
mul.c: In function 'main':
mul.c:80:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |  scanf("%d%d%s%s", &n, &m, aa, bb);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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