結果
問題 | No.1299 Random Array Score |
ユーザー |
![]() |
提出日時 | 2020-11-27 23:08:02 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 95 ms / 2,000 ms |
コード長 | 2,231 bytes |
コンパイル時間 | 343 ms |
コンパイル使用メモリ | 82,588 KB |
実行使用メモリ | 102,332 KB |
最終ジャッジ日時 | 2024-07-26 19:29:08 |
合計ジャッジ時間 | 4,435 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
import sysdef input(): return sys.stdin.readline().strip()def list2d(a, b, c): return [[c] * b for i in range(a)]def list3d(a, b, c, d): return [[[d] * c for k in range(b)] for i in range(a)]def list4d(a, b, c, d, e): return [[[[e] * d for k in range(c)] for k in range(b)] for i in range(a)]def ceil(x, y=1): return int(-(-x // y))def INT(): return int(input())def MAP(): return map(int, input().split())def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]def Yes(): print('Yes')def No(): print('No')def YES(): print('YES')def NO(): print('NO')sys.setrecursionlimit(10**9)INF = 10**19MOD = 998244353EPS = 10**-10def div(x, y, MOD): return x * pow(y, MOD-2, MOD) % MODdef mat_pow(mat, init, K, MOD):""" 行列累乗 """def mat_dot(A, B, MOD):""" 行列の積 """if not isinstance(A[0], list) and not isinstance(A[0], tuple):A = [A]if not isinstance(B[0], list) and not isinstance(A[0], tuple):B = [[b] for b in B]n1 = len(A)n2 = len(A[0])_ = len(B)m2 = len(B[0])res = list2d(n1, m2, 0)for i in range(n1):for j in range(m2):for k in range(n2):res[i][j] += A[i][k] * B[k][j]res[i][j] %= MODreturn resdef _mat_pow(mat, k, MOD):""" 行列matをk乗する """n = len(mat)res = list2d(n, n, 0)for i in range(n):res[i][i] = 1while k > 0:if k & 1:res = mat_dot(res, mat, MOD)mat = mat_dot(mat, mat, MOD)k >>= 1return resres = _mat_pow(mat, K, MOD)res = mat_dot(res, init, MOD)return [a[0] for a in res]N, K = MAP()A = LIST()# dp0 = [0] * (K+1)# dp1 = [0] * (K+1)# dp0[0] = sum(A) % MOD# dp1[0] = div(sum(A), N, MOD)# for i in range(K):# dp0[i+1] = dp0[i] + dp1[i]*N# dp0[i+1] %= MOD# dp1[i+1] = (dp0[i] + dp1[i]*N) / N# dp1[i+1] %= MOD# ans = dp0[K]# print(ans)invN = div(1, N, MOD)mat = [[1, N],[invN, 1],]init = [sum(A) % MOD, div(sum(A), N, MOD)]res = mat_pow(mat, init, K, MOD)print(res[0])