結果

問題 No.1839 Concatenation Matrix
ユーザー 👑 ygussanyygussany
提出日時 2022-01-16 22:51:16
言語 C
(gcc 12.3.0)
結果
AC  
実行時間 913 ms / 3,500 ms
コード長 4,352 bytes
コンパイル時間 2,796 ms
コンパイル使用メモリ 32,488 KB
実行使用メモリ 162,288 KB
最終ジャッジ日時 2023-08-15 06:49:06
合計ジャッジ時間 11,652 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 6 ms
28,544 KB
testcase_01 AC 7 ms
36,672 KB
testcase_02 AC 9 ms
44,844 KB
testcase_03 AC 4 ms
20,328 KB
testcase_04 AC 6 ms
30,508 KB
testcase_05 AC 8 ms
34,720 KB
testcase_06 AC 7 ms
36,688 KB
testcase_07 AC 17 ms
75,660 KB
testcase_08 AC 21 ms
77,864 KB
testcase_09 AC 25 ms
78,208 KB
testcase_10 AC 203 ms
114,320 KB
testcase_11 AC 913 ms
162,148 KB
testcase_12 AC 846 ms
162,288 KB
testcase_13 AC 826 ms
161,044 KB
testcase_14 AC 845 ms
160,968 KB
testcase_15 AC 837 ms
161,108 KB
testcase_16 AC 456 ms
150,020 KB
testcase_17 AC 481 ms
149,696 KB
testcase_18 AC 596 ms
160,612 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

const int Mod = 998244353,
	bit[21] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576},
	bit_inv[21] = {1, 499122177, 748683265, 873463809, 935854081, 967049217, 982646785, 990445569, 994344961, 996294657, 997269505, 997756929, 998000641, 998122497, 998183425, 998213889, 998229121, 998236737, 998240545, 998242449, 998243401},
	root[21] = {1, 998244352, 911660635, 372528824, 929031873, 452798380, 922799308, 781712469, 476477967, 166035806, 258648936, 584193783, 63912897, 350007156, 666702199, 968855178, 629671588, 24514907, 996173970, 363395222, 565042129},
	root_inv[21] = {1, 998244352, 86583718, 509520358, 337190230, 87557064, 609441965, 135236158, 304459705, 685443576, 381598368, 335559352, 129292727, 358024708, 814576206, 708402881, 283043518, 3707709, 121392023, 704923114, 950391366};
int ntt_b[21][1048576], ntt_c[21][1048576], ntt_x[21][1048576], ntt_y[21][1048576];

long long div_mod(long long x, long long y, long long z)
{
	if (x % y == 0) return x / y;
	else return (div_mod((1 + x / y) * y - x, (z % y), y) * z + x) / y;
}
	
void NTT(int k, int a[], int z[])
{
	if (k == 0) {
		z[0] = a[0];
		return;
	}
	
	int i, d = bit[k-1], tmpp;
	long long tmp;
	for (i = 0; i < d; i++) {
		ntt_b[k][i] = a[i*2];
		ntt_c[k][i] = a[i*2+1];
	}
	NTT(k - 1, ntt_b[k], ntt_x[k]);
	NTT(k - 1, ntt_c[k], ntt_y[k]);
	for (i = 0, tmp = 1; i < d; i++, tmp = tmp * root[k] % Mod) {
		tmpp = tmp * ntt_y[k][i] % Mod;
		z[i] = ntt_x[k][i] + tmpp;
		if (z[i] >= Mod) z[i] -= Mod;
		z[i+d] = ntt_x[k][i] - tmpp;
		if (z[i+d] < 0) z[i+d] += Mod;
	}
}

void NTT_reverse(int k, int z[], int a[])
{
	if (k == 0) {
		a[0] = z[0];
		return;
	}
	
	int i, d = bit[k-1], tmpp;
	long long tmp;
	for (i = 0; i < d; i++) {
		ntt_x[k][i] = z[i*2];
		ntt_y[k][i] = z[i*2+1];
	}
	NTT_reverse(k - 1, ntt_x[k], ntt_b[k]);
	NTT_reverse(k - 1, ntt_y[k], ntt_c[k]);
	for (i = 0, tmp = 1; i < d; i++, tmp = tmp * root_inv[k] % Mod) {
		tmpp = tmp * ntt_c[k][i] % Mod;
		a[i] = ntt_b[k][i] + tmpp;
		if (a[i] >= Mod) a[i] -= Mod;
		a[i+d] = ntt_b[k][i] - tmpp;
		if (a[i+d] < 0) a[i+d] += Mod;
	}
}

void prod_poly_NTT(int da, int db, int a[], int b[], int c[])
{
	int i, k;
	for (k = 0; bit[k] < da + db - 1; k++);
	for (i = da; i < bit[k]; i++) a[i] = 0;
	for (i = db; i < bit[k]; i++) b[i] = 0;
	
	int *x = (int*)malloc(sizeof(int) * bit[k]), *y = (int*)malloc(sizeof(int) * bit[k]), *z = (int*)malloc(sizeof(int) * bit[k]);
	NTT(k, a, x);
	NTT(k, b, y);
	for (i = 0; i < bit[k]; i++) z[i] = (long long)x[i] * y[i] % Mod;
	NTT_reverse(k, z, c);
	for (i = 0; i < da + db - 1; i++) c[i] = (long long)c[i] * bit_inv[k] % Mod;
	
	free(x);
	free(y);
	free(z);
}

const int THR = 1000;

// Compute the values b[0-N] of elementary symmetric polynomials of a[1-N] in O(N * (log N)^2) time
void elementary_symmetric_polynomial(int N, int a[], int b[])
{
	int i, j, deg[200001], *x[200001], head, tail, tmp[3][262144];
	for (i = 1; i <= N; i++) {
		deg[i] = 1;
		x[i] = (int*)malloc(sizeof(int) * (deg[i] + 1));
		x[i][0] = 1;
		x[i][1] = a[i];
	}
	for (head = 1, tail = N; head < tail; head += 2) {
		deg[++tail] = deg[head] + deg[head+1];
		x[tail] = (int*)malloc(sizeof(int) * (deg[tail] + 1));
		if (deg[tail] <= THR) {
			for (i = 0; i <= deg[tail]; i++) x[tail][i] = 0;
			for (i = 0; i <= deg[head]; i++) {
				for (j = 0; j <= deg[head+1]; j++) {
					x[tail][i+j] += (long long)x[head][i] * x[head+1][j] % Mod;
					if (x[tail][i+j] >= Mod) x[tail][i+j] -= Mod;
				}
			}
		} else {
			for (i = 0; i <= deg[head]; i++) tmp[0][i] = x[head][i];
			for (i = 0; i <= deg[head+1]; i++) tmp[1][i] = x[head+1][i];
			prod_poly_NTT(deg[head] + 1, deg[head+1] + 1, tmp[0], tmp[1], tmp[2]);
			for (i = 0; i <= deg[tail]; i++) x[tail][i] = tmp[2][i];
		}
		free(x[head]);
		free(x[head+1]);
	}
	for (i = 0; i <= N; i++) b[i] = x[tail][i];
	free(x[tail]);
}

int main()
{
	int i, N, a[262144];
	scanf("%d", &N);
	for (i = 1, a[0] = 0; i <= N; i++) scanf("%d", &(a[i]));
	
	int j, b[262144], c[262144], pow[100001];
	for (i = 2, pow[1] = 10; i < N; i++) pow[i] = (long long)pow[i-1] * pow[i-1] % Mod;
	elementary_symmetric_polynomial(N - 1, pow, b);
	prod_poly_NTT(N + 1, N, a, b, c);
	for (i = 0; i < N; i++) printf("%d\n", (c[i] + c[i+N]) % Mod);
	fflush(stdout);
	return 0;
}
0