Contest Duration: ~ (local time) (100 minutes) Back to Home

Submission #17355625

Source Code Expand

Copy
```import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

MOD = 998_244_353

@njit((i8, i8[:]), cache=True)
def main(N, AB):
pow2 = np.ones(1 << 15, np.int64)
for n in range(1, 1 << 15):
pow2[n] = pow2[n - 1] + pow2[n - 1]
if pow2[n] >= MOD:
pow2[n] -= MOD
A, B = AB[::2] - 1, AB[1::2] - 1
G = np.zeros((N, N), np.int64)
for i in range(len(A)):
a, b = A[i], B[i]
G[a, b] = G[b, a] = 1
dp0 = np.zeros((1 << N), np.int64)  # 集合に対して、その中におさまっている辺の数
for s in range(1 << N):
for v in range(N):
if not s & 1 << v:
continue
for w in range(v + 1, N):
if not s & 1 << w:
continue
dp0[s] += G[v, w]
dp1 = np.zeros(1 << N, np.int64)  # S をラベル付き二部グラフにする方法
dp1[0] = 1
for s in range(1 << N):
t = s
while True:
u = s ^ t
# (u,t) 辺を数える
e = 0
for v in range(N):
"""(t, u) 辺の個数を数える
if u & 1 << v:
e += dp0[t, v]"""
e = dp0[u + t] - dp0[u] - dp0[t]
dp1[s] += pow2[e]
if t == 0:
break
t = (t - 1) & s
dp1[s] %= MOD
dp2 = np.zeros(1 << N, np.int64)  # S をラベル付き連結二部グラフにする方法
for s in range(1, 1 << N):
for v0 in range(N):
if s & 1 << v0:
break
# v0 を含む連結成分が t
x = dp1[s]
t = s
while t:
t = (t - 1) & s
if t & 1 << v0:
u = s ^ t
x -= dp2[t] * dp1[u] % MOD
dp2[s] = x % MOD
ans = dp2[-1]
if ans & 1:
ans += MOD
return ans >> 1

print(main(N, AB))```

#### Submission Info

Submission Time 2020-10-12 01:30:54+0900 F - Lights Out on Connected Graph maspy Python (3.8.2) 900 2189 Byte AC 1086 ms 108288 KB

#### Judge Result

Set Name Sample All
Score / Max Score 0 / 0 900 / 900
Status
 AC × 3
 AC × 33
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt, random_25.txt, random_26.txt, random_27.txt, random_28.txt, random_29.txt, random_30.txt, sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
random_01.txt 1086 ms 108240 KB
random_02.txt 1077 ms 107520 KB
random_03.txt 1080 ms 108208 KB
random_04.txt 1079 ms 107000 KB
random_05.txt 1081 ms 108248 KB
random_06.txt 1071 ms 107152 KB
random_07.txt 1078 ms 108252 KB
random_08.txt 1073 ms 108288 KB
random_09.txt 1078 ms 107216 KB
random_10.txt 1076 ms 108212 KB
random_11.txt 473 ms 105832 KB
random_12.txt 464 ms 105592 KB
random_13.txt 456 ms 106376 KB
random_14.txt 451 ms 105492 KB
random_15.txt 451 ms 105800 KB
random_16.txt 458 ms 106392 KB
random_17.txt 453 ms 105596 KB
random_18.txt 456 ms 106312 KB
random_19.txt 452 ms 106396 KB
random_20.txt 453 ms 105832 KB
random_21.txt 481 ms 106536 KB
random_22.txt 455 ms 105832 KB
random_23.txt 453 ms 106408 KB
random_24.txt 455 ms 106324 KB
random_25.txt 633 ms 106676 KB
random_26.txt 453 ms 105820 KB
random_27.txt 454 ms 105848 KB
random_28.txt 451 ms 106332 KB
random_29.txt 1061 ms 108196 KB
random_30.txt 472 ms 106284 KB
sample_01.txt 465 ms 105672 KB
sample_02.txt 464 ms 105592 KB
sample_03.txt 1062 ms 107776 KB