結果
問題 | No.2504 NOT Path Painting |
ユーザー |
|
提出日時 | 2023-10-13 22:39:28 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 782 ms / 2,000 ms |
コード長 | 2,137 bytes |
コンパイル時間 | 340 ms |
コンパイル使用メモリ | 82,452 KB |
実行使用メモリ | 107,156 KB |
最終ジャッジ日時 | 2024-09-15 18:24:47 |
合計ジャッジ時間 | 14,359 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
import sysfrom itertools import permutationsimport heapqfrom collections import dequeimport randominput = lambda :sys.stdin.readline().rstrip()mi = lambda :map(int,input().split())li = lambda :list(mi())mod = 998244353def solve_brute(n,edge):res = 1deq = deque([0])topo = []parent = [-1] * nwhile deq:v = deq.popleft()topo.append(v)for nv in edge[v]:if nv == parent[v]:continueparent[nv] = vdeq.append(nv)sz = [1] * nfor v in topo[::-1]:for nv in edge[v]:if nv == parent[v]:continuesz[v] += sz[nv]ok = n * (n+1)//2 - (n-sz[v]) * (n-sz[v]+1) //2for nv in edge[v]:if nv == parent[v]:continueok -= sz[nv] * (sz[nv]+1) // 2res += ok * pow(n*(n+1)//2-ok,mod-2,mod)res %= modfor v in range(1,n):s = sz[v]t = N - sz[v]ok = s * tres -= ok * pow(n*(n+1)//2-ok,mod-2,mod)res %= modreturn res % moddef 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)//2dp[i][i] = N*(N+1)//2 * pow(k,mod-2,mod) % modfor l in range(N)[::-1]:for r in range(l+1,N):a,b = 0,0for 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 %= modelse:a += 1dp[l][r] = (b+1) * inv(1-(a * inv(N*(N+1)//2))) % modreturn 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))