結果
問題 | No.2504 NOT Path Painting |
ユーザー | chineristAC |
提出日時 | 2023-10-13 22:39:28 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 885 ms / 2,000 ms |
コード長 | 2,137 bytes |
コンパイル時間 | 515 ms |
コンパイル使用メモリ | 87,280 KB |
実行使用メモリ | 110,112 KB |
最終ジャッジ日時 | 2023-10-13 22:40:04 |
合計ジャッジ時間 | 16,843 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 112 ms
73,080 KB |
testcase_01 | AC | 679 ms
82,376 KB |
testcase_02 | AC | 630 ms
82,316 KB |
testcase_03 | AC | 633 ms
81,504 KB |
testcase_04 | AC | 650 ms
82,036 KB |
testcase_05 | AC | 628 ms
81,996 KB |
testcase_06 | AC | 621 ms
81,840 KB |
testcase_07 | AC | 642 ms
82,124 KB |
testcase_08 | AC | 614 ms
81,584 KB |
testcase_09 | AC | 610 ms
81,472 KB |
testcase_10 | AC | 649 ms
81,204 KB |
testcase_11 | AC | 627 ms
81,976 KB |
testcase_12 | AC | 657 ms
82,688 KB |
testcase_13 | AC | 640 ms
81,612 KB |
testcase_14 | AC | 653 ms
82,752 KB |
testcase_15 | AC | 813 ms
104,804 KB |
testcase_16 | AC | 885 ms
110,112 KB |
testcase_17 | AC | 837 ms
108,200 KB |
testcase_18 | AC | 748 ms
109,392 KB |
testcase_19 | AC | 850 ms
107,764 KB |
testcase_20 | AC | 746 ms
106,892 KB |
ソースコード
import sys from itertools import permutations import heapq from collections import deque import random input = lambda :sys.stdin.readline().rstrip() mi = lambda :map(int,input().split()) li = lambda :list(mi()) mod = 998244353 def solve_brute(n,edge): res = 1 deq = deque([0]) topo = [] parent = [-1] * n while deq: v = deq.popleft() topo.append(v) for nv in edge[v]: if nv == parent[v]: continue parent[nv] = v deq.append(nv) sz = [1] * n for v in topo[::-1]: for nv in edge[v]: if nv == parent[v]: continue sz[v] += sz[nv] ok = n * (n+1)//2 - (n-sz[v]) * (n-sz[v]+1) //2 for nv in edge[v]: if nv == parent[v]: continue ok -= sz[nv] * (sz[nv]+1) // 2 res += ok * pow(n*(n+1)//2-ok,mod-2,mod) res %= mod for v in range(1,n): s = sz[v] t = N - sz[v] ok = s * t res -= ok * pow(n*(n+1)//2-ok,mod-2,mod) res %= mod return res % mod def brute(N): def inv(r): return pow(r,mod-2,mod) dp = [[0]*N for i in range(N)] for i in range(N): k = i * (i+1) //2 + (N-i-1) * (N-i)//2 dp[i][i] = N*(N+1)//2 * pow(k,mod-2,mod) % mod for l in range(N)[::-1]: for r in range(l+1,N): a,b = 0,0 for x in range(N): for y in range(x,N): nl,nr = max(l,x),min(r,y) if (nl,nr)!=(l,r): b += dp[nl][nr] * inv(N*(N+1)//2) b %= mod else: a += 1 dp[l][r] = (b+1) * inv(1-(a * inv(N*(N+1)//2))) % mod return dp[0][N-1] for _ in range(int(input())): N = int(input()) edge = [[] for v in range(N)] for _ in range(N-1): u,v = mi() edge[u-1].append(v-1) edge[v-1].append(u-1) print(solve_brute(N,edge))