結果

問題 No.2582 Random Average^K
ユーザー chineristAC
提出日時 2023-12-10 00:10:02
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,540 ms / 2,000 ms
コード長 1,130 bytes
コンパイル時間 261 ms
コンパイル使用メモリ 82,312 KB
実行使用メモリ 321,980 KB
最終ジャッジ日時 2025-02-21 06:13:00
合計ジャッジ時間 22,422 ms
ジャッジサーバーID
(参考情報)
judge4 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import sys
from itertools import permutations
from heapq import heappop,heappush
from collections import deque
import random
import bisect
input = lambda :sys.stdin.readline().rstrip()
mi = lambda :map(int,input().split())
li = lambda :list(mi())
"""
E[prod x_i^a_i] = prod 1/(ai+1)
sum a_i = K a
K! * prod 1/(ai+1)!
1/1!+x/2!+x^2/3!+... = (e^x-1)/x
K! [x^K] (e^x-1)^N/x^N
= K! [x^(N+K)] (e^x-1)^N
"""
def cmb(n, r, mod):
if ( r<0 or r>n ):
return 0
return (g1[n] * g2[r] % mod) * g2[n-r] % mod
mod = 998244353
N = 10**6 + 100 + 10**7
g1 = [1]*(N+1)
g2 = [1]*(N+1)
inverse = [1]*(N+1)
for i in range( 2, N + 1 ):
g1[i]=( ( g1[i-1] * i ) % mod )
inverse[i]=( ( -inverse[mod % i] * (mod//i) ) % mod )
g2[i]=( (g2[i-1] * inverse[i]) % mod )
inverse[0]=0
N,K = mi()
res = 0
for i in range(N+1):
if (N-i) & 1:
res -= cmb(N,i,mod) * pow(i,N+K,mod) % mod
else:
res += cmb(N,i,mod) * pow(i,N+K,mod) % mod
res %= mod
res *= g1[K] * g2[N+K] % mod
res %= mod
res *= pow(inverse[N],K,mod)
res %= mod
print(res % mod)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0