結果

問題 No.1050 Zero (Maximum)
ユーザー convexineqconvexineq
提出日時 2020-05-08 22:03:00
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 1,215 ms / 2,000 ms
コード長 966 bytes
コンパイル時間 74 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 11,008 KB
最終ジャッジ日時 2024-07-04 00:41:58
合計ジャッジ時間 7,844 ms
ジャッジサーバーID
(参考情報)
judge2 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

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

MOD=10**9+7
def matmul(A,B,mod): # A,B:
res = [[0]*len(B[0]) for _ in [None]*len(A)]
for i, resi in enumerate(res):
for k, aik in enumerate(A[i]):
for j,bkj in enumerate(B[k]):
resi[j] += aik*bkj
resi[j] %= mod
return res
def matpow(A,p,M): #A^p mod M
if p%2:
return matmul(A, matpow(A,p-1,M), M)
elif p > 0:
b = matpow(A,p//2,M)
return matmul(b,b,M)
else:
return [[1 if i == j else 0 for j in range(len(A))] for i in range(len(A))]
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
m,k = [int(i) for i in read().split()]
mat = [[0]*m for _ in range(m)]
for i in range(m):
for j in range(m):
mat[(i+j)%m][i] += 1
mat[(i*j)%m][i] += 1
#print(mat)
v = [[0] for _ in range(m)]
v[0][0] = 1
v = matmul(matpow(mat,k,MOD), v,MOD)
print(v[0][0])
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0