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

Submission #17456186

Source Code Expand

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

MOD = 1_000_000_007

@njit((i8, i8), cache=True)
def mpow(a, n):
p = 1
while n:
if n & 1:
p = p * a % MOD
a = a * a % MOD
n >>= 1
return p

@njit((i8, ), cache=True)
def fact_table(N):
N += 1
fact = np.empty(N, np.int64)
fact[0] = 1
for n in range(1, N):
fact[n] = n * fact[n - 1] % MOD
fact_inv = np.empty(N, np.int64)
fact_inv[N - 1] = mpow(fact[N - 1], MOD - 2)
for n in range(N - 1, 0, -1):
fact_inv[n - 1] = fact_inv[n] * n % MOD
inv = np.empty(N, np.int64)
inv[0] = 0
inv[1:] = fact[:-1] * fact_inv[1:] % MOD
return fact, fact_inv, inv

@njit((i8, i8, i8), cache=True)
def main(N, M, L):
"""連結成分の大きさ L 以下
成分 k 個に分ける方法 dp[n,k]
"""
fact, fact_inv, inv = fact_table(N + 10)

def C(n, k):
if k < 0 or k > n:
return 0
return fact[n] * fact_inv[k] % MOD * fact_inv[n - k] % MOD

def f(n):
# ちょうど n 点をえらんだとき、それら n 点からなる連結成分の作り方
if n > L:
return 0, 0
if n == 1:
return 1, 0
if n == 2:
return 1, 1
# パス
p = fact[n] * inv[2] % MOD
# サイクル
c = fact[n - 1] * inv[2] % MOD
return p, c

dp = np.zeros((N + 1, N + 1), np.int64)
dp[0, 0] = 1
for n in range(1, N + 1):
for k in range(1, n + 1):
# 頂点 0 を含む成分の大きさが k
choose = C(n - 1, k - 1)
p, c = f(k)
p, c = p * choose % MOD, c * choose % MOD
for size in range(N + 1):
if size + k - 1 <= N:
dp[n, size + k - 1] += dp[n - k, size] * p
dp[n, size + k - 1] %= MOD
if size + k <= N:
dp[n, size + k] += dp[n - k, size] * c
dp[n, size + k] %= MOD
return dp[N, M]

N, M, L = map(int, readline().split())

ans = main(N, M, L) - main(N, M, L - 1)
print(ans % MOD)```

#### Submission Info

Submission Time 2020-10-17 20:25:14+0900 F - Unbranched maspy Python (3.8.2) 600 2363 Byte AC 662 ms 107900 KB

#### Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
 AC × 3
 AC × 40
Set Name Test Cases
Sample sample00, sample01, sample02
All case03, case04, case05, case06, case07, case08, case09, case10, case11, case12, case13, case14, case15, case16, case17, case18, case19, case20, case21, case22, case23, case24, case25, case26, case27, case28, case29, case30, case31, case32, case33, case34, case35, case36, case37, case38, case39, sample00, sample01, sample02
Case Name Status Exec Time Memory
case03 578 ms 106500 KB
case04 554 ms 106760 KB
case05 564 ms 106524 KB
case06 553 ms 106472 KB
case07 560 ms 106484 KB
case08 567 ms 106560 KB
case09 563 ms 106708 KB
case10 562 ms 106456 KB
case11 554 ms 106056 KB
case12 556 ms 106708 KB
case13 550 ms 106684 KB
case14 543 ms 106524 KB
case15 547 ms 106520 KB
case16 661 ms 107240 KB
case17 642 ms 107416 KB
case18 554 ms 106836 KB
case19 587 ms 106816 KB
case20 620 ms 106552 KB
case21 602 ms 107220 KB
case22 566 ms 106696 KB
case23 599 ms 107188 KB
case24 606 ms 106940 KB
case25 623 ms 107188 KB
case26 557 ms 106704 KB
case27 566 ms 107340 KB
case28 573 ms 106676 KB
case29 658 ms 107900 KB
case30 628 ms 107108 KB
case31 567 ms 106856 KB
case32 558 ms 106524 KB
case33 622 ms 107012 KB
case34 565 ms 107376 KB
case35 582 ms 106244 KB
case36 586 ms 106288 KB
case37 644 ms 107144 KB
case38 567 ms 106664 KB
case39 554 ms 106504 KB
sample00 558 ms 106052 KB
sample01 559 ms 106688 KB
sample02 662 ms 107388 KB