結果
問題 | No.1614 Majority Painting on Tree |
ユーザー | 👑 ygussany |
提出日時 | 2021-06-12 19:17:43 |
言語 | C (gcc 12.3.0) |
結果 |
AC
|
実行時間 | 1,211 ms / 5,000 ms |
コード長 | 2,536 bytes |
コンパイル時間 | 372 ms |
コンパイル使用メモリ | 31,800 KB |
実行使用メモリ | 10,468 KB |
最終ジャッジ日時 | 2023-09-24 14:29:43 |
合計ジャッジ時間 | 18,383 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 710 ms
10,316 KB |
testcase_01 | AC | 240 ms
10,428 KB |
testcase_02 | AC | 274 ms
10,380 KB |
testcase_03 | AC | 620 ms
10,372 KB |
testcase_04 | AC | 756 ms
10,424 KB |
testcase_05 | AC | 709 ms
10,316 KB |
testcase_06 | AC | 851 ms
10,464 KB |
testcase_07 | AC | 592 ms
10,312 KB |
testcase_08 | AC | 380 ms
10,316 KB |
testcase_09 | AC | 408 ms
10,468 KB |
testcase_10 | AC | 123 ms
10,396 KB |
testcase_11 | AC | 489 ms
10,376 KB |
testcase_12 | AC | 537 ms
10,440 KB |
testcase_13 | AC | 386 ms
10,308 KB |
testcase_14 | AC | 755 ms
10,452 KB |
testcase_15 | AC | 704 ms
10,368 KB |
testcase_16 | AC | 183 ms
10,384 KB |
testcase_17 | AC | 342 ms
10,428 KB |
testcase_18 | AC | 459 ms
10,456 KB |
testcase_19 | AC | 194 ms
10,460 KB |
testcase_20 | AC | 1,045 ms
10,460 KB |
testcase_21 | AC | 1,121 ms
10,372 KB |
testcase_22 | AC | 1,211 ms
10,368 KB |
testcase_23 | AC | 141 ms
10,312 KB |
testcase_24 | AC | 1,098 ms
10,384 KB |
testcase_25 | AC | 260 ms
10,392 KB |
testcase_26 | AC | 670 ms
10,316 KB |
testcase_27 | AC | 2 ms
4,632 KB |
testcase_28 | AC | 2 ms
4,784 KB |
testcase_29 | AC | 2 ms
6,356 KB |
testcase_30 | AC | 2 ms
6,308 KB |
testcase_31 | AC | 2 ms
4,776 KB |
testcase_32 | AC | 2 ms
4,760 KB |
testcase_33 | AC | 2 ms
4,776 KB |
testcase_34 | AC | 2 ms
6,092 KB |
testcase_35 | AC | 2 ms
4,704 KB |
testcase_36 | AC | 2 ms
4,664 KB |
testcase_37 | AC | 2 ms
4,644 KB |
testcase_38 | AC | 1 ms
6,272 KB |
testcase_39 | AC | 2 ms
4,684 KB |
testcase_40 | AC | 2 ms
4,728 KB |
testcase_41 | AC | 1 ms
4,644 KB |
testcase_42 | AC | 1 ms
6,408 KB |
testcase_43 | AC | 1 ms
6,316 KB |
testcase_44 | AC | 1 ms
4,684 KB |
testcase_45 | AC | 2 ms
6,680 KB |
testcase_46 | AC | 2 ms
4,660 KB |
testcase_47 | AC | 1 ms
4,716 KB |
testcase_48 | AC | 1 ms
4,680 KB |
コンパイルメッセージ
main.c:4:43: 警告: 組み込み関数 ‘pow’ が非関数として宣言されました [-Wbuiltin-declaration-mismatch] 4 | long long fact[100001], fact_inv[100001], pow[2][100001]; | ^~~
ソースコード
#include <stdio.h> const int Mod = 998244353; long long fact[100001], fact_inv[100001], pow[2][100001]; 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; } long long combination(int n, int k) { return fact[n] * fact_inv[k] % Mod * fact_inv[n-k] % Mod; } typedef struct List { struct List *next; int v; } list; long long solve(int N, int C, list* adj[]) { if (C == 1) return 1; int i, r = 1, u, w, head, tail; static int par[100001] = {}, q[100001]; list *p; if (par[r] == 0) { par[r] = r; q[0] = r; 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; } } } } else head = N; int k; static long long dp[100001], prod; for (head--; head > 0; head--) { u = q[head]; for (p = adj[u], k = 0, prod = 1; p != NULL; p = p->next) { w = p->v; if (w == par[u]) continue; prod = prod * dp[w] % Mod; k++; } dp[u] = pow[0][k]; for (i = (k + 1) / 2; i < k; i++) dp[u] += Mod - combination(k, i) * pow[1][k-i] % Mod; for (i = (k + 3) / 2; i <= k; i++) dp[u] += Mod - combination(k, i) * pow[1][k-i+1] % Mod; dp[u] = dp[u] % Mod * prod % Mod; } for (p = adj[r], k = 0, prod = 1; p != NULL; p = p->next) { w = p->v; prod = prod * dp[w] % Mod; k++; } dp[r] = pow[0][k-1]; for (i = k / 2 + 1; i < k; i++) dp[r] += Mod - combination(k, i) * pow[1][k-i] % Mod; return dp[r] % Mod * prod % Mod * C % Mod; } int main() { int i, k, N, C, u, w; list *adj[100001] = {}, e[200001]; scanf("%d %d", &N, &C); 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]); } for (i = 1, fact[0] = 1; i <= N; i++) fact[i] = fact[i-1] * i % Mod; for (i = N - 1, fact_inv[N] = div_mod(1, fact[N], Mod); i >= 0; i--) fact_inv[i] = fact_inv[i+1] * (i + 1) % Mod; for (k = 1, pow[1][0] = 1; k <= N; k++) pow[1][k] = pow[1][k-1] * C % Mod; long long ans = 0; for (i = C; i >= 1; i--) { for (k = 0; k <= N; k++) pow[0][k] = pow[1][k]; for (k = 1, pow[1][0] = 1; k <= N; k++) pow[1][k] = pow[1][k-1] * (i - 1) % Mod; if ((C - i) % 2 == 0) ans += solve(N, i, adj) * combination(C, i) % Mod; else ans += Mod - solve(N, i, adj) * combination(C, i) % Mod; } printf("%lld\n", ans % Mod); fflush(stdout); return 0; }