Submission #3270688
Source Code Expand
import sys
stdin = sys.stdin
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())
# nの逆元のリスト
def inv_mod(n:int, mod:int) -> list:
inv = [0,1]
for i in range(2,n+1):
inv.append(mod - ((mod//i)*inv[mod%i]) % mod)
return inv
# nの階乗のリスト
def fact(n:int, mod:int) -> list:
fac = [1,1]
res = 1
for i in range(2,n+1):
res = res*i%mod
fac.append(res)
return fac
# nの階乗の逆元のリスト
def fact_inv(n:int, inv:list, mod:int) -> list:
facInv = [1,1]
for i in range(2,n+1):
facInv.append(facInv[i-1]*inv[i] % mod)
return facInv
# 二項係数
def nCr(n:int, r:int, mod:int, fac:list, facInv:list) -> int:
if not (0<=r and r<=n):
return 0
return ((fac[n]*facInv[r]) % mod) * facInv[n-r] % mod
MOD = 998244353
k,n = li()
inv = inv_mod(n+k,MOD)
fac = fact(n+k,MOD)
facInv = fact_inv(n+k,inv,MOD)
answers = []
if k == 1:
print(0)
else:
for t in range(2,k+2):
p = t//2
ans = 0
if t%2 == 0:
temp = 0
for q in range(p):
temp = temp + nCr(p-1,q,MOD,fac,facInv) \
* (2**q) \
* nCr(n+k-2*p,n-q,MOD,fac,facInv)
temp %= MOD
temp = temp + nCr(p-1,q,MOD,fac,facInv) \
* (2**q) \
* nCr(n+k-2*p-1,n-q-1,MOD,fac,facInv)
temp %= MOD
ans = temp%MOD
else:
temp = 0
for q in range(p+1):
temp = temp + nCr(p,q,MOD,fac,facInv) \
* (2**q) \
* nCr(n+k-2*p-1,n-q,MOD,fac,facInv)
temp %= MOD
ans = temp%MOD
answers.append(ans)
print(ans)
for ans in answers[-2::-1]:
print(ans)
Submission Info
Submission Time |
|
Task |
E - Stop. Otherwise... |
User |
polarbear08 |
Language |
Python (3.4.3) |
Score |
0 |
Code Size |
2387 Byte |
Status |
TLE |
Exec Time |
2104 ms |
Memory |
3728 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 700 |
Status |
|
|
Set Name |
Test Cases |
Sample |
s1.txt, s2.txt, s3.txt |
All |
01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, s1.txt, s2.txt, s3.txt |
Case Name |
Status |
Exec Time |
Memory |
01.txt |
TLE |
2104 ms |
3720 KB |
02.txt |
TLE |
2104 ms |
3700 KB |
03.txt |
TLE |
2104 ms |
3572 KB |
04.txt |
AC |
19 ms |
3316 KB |
05.txt |
TLE |
2104 ms |
3568 KB |
06.txt |
TLE |
2104 ms |
3572 KB |
07.txt |
TLE |
2104 ms |
3728 KB |
08.txt |
AC |
445 ms |
3572 KB |
09.txt |
AC |
18 ms |
3192 KB |
10.txt |
AC |
1368 ms |
3508 KB |
11.txt |
TLE |
2103 ms |
3444 KB |
12.txt |
AC |
19 ms |
3192 KB |
13.txt |
AC |
354 ms |
3316 KB |
14.txt |
TLE |
2104 ms |
3572 KB |
15.txt |
TLE |
2104 ms |
3700 KB |
16.txt |
TLE |
2104 ms |
3700 KB |
17.txt |
AC |
17 ms |
3192 KB |
18.txt |
AC |
17 ms |
3192 KB |
19.txt |
AC |
17 ms |
3192 KB |
20.txt |
AC |
17 ms |
3192 KB |
s1.txt |
AC |
18 ms |
3192 KB |
s2.txt |
AC |
18 ms |
3192 KB |
s3.txt |
AC |
18 ms |
3192 KB |