結果

問題 No.2214 Products on Tree
ユーザー ygussanyygussany
提出日時 2023-02-04 12:06:31
言語 C
(gcc 12.3.0)
結果
WA  
実行時間 -
コード長 7,168 bytes
コンパイル時間 1,192 ms
コンパイル使用メモリ 34,688 KB
実行使用メモリ 63,880 KB
最終ジャッジ日時 2024-07-03 10:22:40
合計ジャッジ時間 29,769 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
17,828 KB
testcase_01 AC 3 ms
10,880 KB
testcase_02 AC 3 ms
10,760 KB
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 AC 4 ms
12,436 KB
testcase_24 AC 4 ms
10,884 KB
testcase_25 AC 3 ms
10,884 KB
testcase_26 AC 4 ms
10,880 KB
testcase_27 AC 3 ms
10,884 KB
testcase_28 TLE -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
権限があれば一括ダウンロードができます

ソースコード

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};

void NTT_inline(int kk, int a[], int x[])
{
	int h, hh, i, ii, j, jj, k, l, r = bit[kk], d = bit[kk-1], tmpp, cur, prev;
	int *pi, *pii, *pj, *pjj;
	static int y[2][1048576];
	long long tmp;
	for (i = 0; i < r; i++) y[0][i] = a[i];
	for (k = 1, kk--, cur = 1, prev = 0; kk >= 0; k++, kk--, cur ^= 1, prev ^= 1) {
		for (h = 0, tmp = 1; h << (kk + 1) < r; h++, tmp = tmp * root[k] % Mod) {
			for (hh = 0, pi = &(y[cur][h<<kk]), pii = pi + d, pj = &(y[prev][h<<(kk+1)]), pjj = pj + bit[kk]; hh < bit[kk]; hh++, pi++, pii++, pj++, pjj++) {
				tmpp = tmp * (*pjj) % Mod;
				*pi = *pj + tmpp;
				if (*pi >= Mod) *pi -= Mod;
				*pii = *pj - tmpp;
				if (*pii < 0) *pii += Mod;
			}
		}
	}
	for (i = 0; i < r; i++) x[i] = y[prev][i];
}

void NTT_reverse_inline(int kk, int a[], int x[])
{
	int h, hh, i, ii, j, jj, k, l, r = bit[kk], d = bit[kk-1], tmpp, cur, prev;
	int *pi, *pii, *pj, *pjj;
	static int y[2][1048576];
	long long tmp;
	for (i = 0; i < r; i++) y[0][i] = a[i];
	for (k = 1, kk--, cur = 1, prev = 0; kk >= 0; k++, kk--, cur ^= 1, prev ^= 1) {
		for (h = 0, tmp = 1; h << (kk + 1) < r; h++, tmp = tmp * root_inv[k] % Mod) {
			for (hh = 0, pi = &(y[cur][h<<kk]), pii = pi + d, pj = &(y[prev][h<<(kk+1)]), pjj = pj + bit[kk]; hh < bit[kk]; hh++, pi++, pii++, pj++, pjj++) {
				tmpp = tmp * (*pjj) % Mod;
				*pi = *pj + tmpp;
				if (*pi >= Mod) *pi -= Mod;
				*pii = *pj - tmpp;
				if (*pii < 0) *pii += Mod;
			}
		}
	}
	for (i = 0; i < r; i++) x[i] = y[prev][i];
}

// Compute the product of two polynomials a[0-da] and b[0-db] using NTT in O(d * log d) time
void prod_poly_NTT(int da, int db, int a[], int b[], int c[])
{
	int i, k;
	static int aa[1048576], bb[1048576], cc[1048576];
	for (k = 0; bit[k] <= da + db; k++);
	for (i = 0; i <= da; i++) aa[i] = a[i];
	for (i = da + 1; i < bit[k]; i++) aa[i] = 0;
	for (i = 0; i <= db; i++) bb[i] = b[i];
	for (i = db + 1; i < bit[k]; i++) bb[i] = 0;
	
	static int x[1048576], y[1048576], z[1048576];
	NTT_inline(k, aa, x);
	if (db == da) {
		for (i = 0; i <= da; i++) if (a[i] != b[i]) break;
		if (i <= da) NTT_inline(k, bb, y);
		else for (i = 0; i < bit[k]; i++) y[i] = x[i];
	} else NTT_inline(k, bb, y);
	for (i = 0; i < bit[k]; i++) z[i] = (long long)x[i] * y[i] % Mod;
	NTT_reverse_inline(k, z, cc);
	for (i = 0; i <= da + db; i++) c[i] = (long long)cc[i] * bit_inv[k] % Mod;
}

// Compute the product of two polynomials a[0-da] and b[0-db] naively in O(da * db) time
void prod_poly_naive(int da, int db, int a[], int b[], int c[])
{
	int i, j;
	static long long tmp[1048576];
	for (i = 0; i <= da + db; i++) tmp[i] = 0;
	for (i = 0; i <= da; i++) for (j = 0; j <= db; j++) tmp[i+j] += (long long)a[i] * b[j] % Mod;
	for (i = 0; i <= da + db; i++) c[i] = tmp[i] % Mod;
}

// Compute the product of two polynomials a[0-da] and b[0-db] in an appropriate way
void prod_polynomial(int da, int db, int a[], int b[], int c[])
{
	if (da <= 70 || db <= 70) prod_poly_naive(da, db, a, b, c);
	else prod_poly_NTT(da, db, a, b, c);
}

typedef struct {
	int key, id;
} data;

typedef struct {
	data obj[200001];
	int size;
} min_heap;

void push(min_heap* h, data x)
{
	int i = ++(h->size), j = i >> 1;
	data tmp;
	h->obj[i] = x;
	while (j > 0) {
		if (h->obj[i].key < h->obj[j].key) {
			tmp = h->obj[j];
			h->obj[j] = h->obj[i];
			h->obj[i] = tmp;
			i = j;
			j >>= 1;
		} else break;
	}
}

data pop(min_heap* h)
{
	int i = 1, j = 2;
	data output = h->obj[1], tmp;
	h->obj[1] = h->obj[(h->size)--];
	while (j <= h->size) {
		if (j < h->size && h->obj[j^1].key < h->obj[j].key) j ^= 1;
		if (h->obj[j].key < h->obj[i].key) {
			tmp = h->obj[j];
			h->obj[j] = h->obj[i];
			h->obj[i] = tmp;
			i = j;
			j <<= 1;
		} else break;
	}
	return output;
}

typedef struct Edge {
	struct Edge *next;
	int v;
} edge;

int main()
{
	int i, N, M, u, w;
	edge *adj[200001] = {}, e[400001], *p;
	scanf("%d", &N);
	for (i = 0; i < N - 1; i++) {
		scanf("%d %d", &u, &w);
		e[i*2].v = w;
		e[i*2+1].v = u;
		e[i*2].next = adj[u];
		e[i*2+1].next = adj[w];
		adj[u] = &(e[i*2]);
		adj[w] = &(e[i*2+1]);
	}
	
	int par[200001] = {}, q[200001], head, tail;
	par[1] = 1;
	q[0] = 1;
	for (head = 0, tail = 1; head < tail; head++) {
		u = q[head];
		for (p = adj[u]; p != NULL; p = p->next) {
			w = p->v;
			if (par[w] == 0) {
				par[w] = u;
				q[tail++] = w;
			}
		}
	}
	
	int j, ww, size[200001], *dp[200001], a[524288], b[524288], c[524288];
	long long tmp;
	min_heap h;
	data d, dd, d_tmp;
	for (head--; head >= 0; head--) {
		u = q[head];
		
		/*
		for (p = adj[u], size[u] = 1; p != NULL; p = p->next) {
			w = p->v;
			if (par[u] == w) continue;
			size[u] += size[w];
		}
		dp[u] = (int*)malloc(sizeof(int) * (size[u] + 1));
		dp[u][0] = 0;
		dp[u][1] = 1;
		for (i = 2; i <= size[u]; i++) dp[u][i] = 0;
		size[u] = 1;
		for (p = adj[u]; p != NULL; p = p->next) {
			w = p->v;
			if (par[u] == w) continue;
			for (i = size[u]; i > 0; i--) {
				for (j = 1, tmp = 0; j <= size[w]; j++) {
					dp[u][i+j] += (long long)dp[u][i] * dp[w][j] % Mod;
					if (dp[u][i+j] >= Mod) dp[u][i+j] -= Mod;
					tmp += (long long)dp[w][j] * j % Mod;
				}
				tmp %= Mod;
				dp[u][i] = dp[u][i] * tmp % Mod;
			}
			size[u] += size[w];
			free(dp[w]);
		}
		*/
		
		h.size = 0;
		d.key = 1;
		d.id = u;
		push(&h, d);
		for (p = adj[u], size[u] = 1; p != NULL; p = p->next) {
			w = p->v;
			if (par[u] == w) continue;
			size[u] += size[w];
			d.key = size[w];
			d.id = w;
			push(&h, d);
		}
		dp[u] = (int*)malloc(sizeof(int) * 2);
		dp[u][0] = 0;
		dp[u][1] = 1;
		
		while (h.size >= 2) {
			d = pop(&h);
			dd = pop(&h);
			w = d.id;
			ww = dd.id;
			
			if (ww == u) {
				w ^= ww;
				ww ^= w;
				w ^= ww;
				d_tmp = dd;
				dd = d;
				d = d_tmp;
			}
			
			prod_polynomial(d.key, dd.key, dp[w], dp[ww], c);
			for (j = 1, tmp = 0; j <= dd.key; j++) tmp += (long long)dp[ww][j] * j % Mod;
			for (i = 0, tmp %= Mod; i <= d.key; i++) dp[w][i] = (c[i] + dp[w][i] * tmp) % Mod;
			d.key += dd.key;
			d.id = w;
			push(&h, d);
			dp[w] = (int*)realloc(dp[w], sizeof(int) * (d.key + 1));
			for (; i <= d.key; i++) dp[w][i] = c[i];
			free(dp[ww]);
		}
	}
	
	long long ans = 0;
	for (i = 1; i <= size[1]; i++) ans += (long long)dp[1][i] * i % Mod;
	printf("%lld\n", ans % Mod);
	fflush(stdout);
	return 0;
}
0