結果
問題 | No.1847 Good Sequence |
ユーザー |
👑 ![]() |
提出日時 | 2021-12-07 11:52:51 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 873 ms / 3,000 ms |
コード長 | 1,013 bytes |
コンパイル時間 | 892 ms |
コンパイル使用メモリ | 82,424 KB |
実行使用メモリ | 76,296 KB |
最終ジャッジ日時 | 2024-10-01 12:34:12 |
合計ジャッジ時間 | 6,962 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 41 |
ソースコード
def mul(p,q,mod):n=len(p)ans=[[0 for i in range(n)] for j in range(n)]for i in range(n):for j in range(n):for k in range(n):ans[i][k]+=(p[i][j]*q[j][k])%modif ans[i][k]>=mod:ans[i][k]-=modreturn ansdef my_pow(p,x,mod):n=len(p)ans=[[0 for i in range(n)]for j in range(n)]for i in range(n):ans[i][i]=1while x>0:if x%2==1:ans=mul(ans,p,mod)x//=2p=mul(p,p,mod)return ansMOD=10**9+7L,N,M=map(int,input().split())K=list(map(int,input().split()))s=set()tmp=0D=sum(K)+M+1base=[[0 for i in range(D)]for j in range(D)]for i in range(M):for j in range(D):if j<tmp or tmp+K[i]+1<=j:base[j][tmp]=1for j in range(K[i]):base[j+tmp][j+1+tmp]=1tmp+=K[i]+1base[tmp-1][tmp-1]=1s.add(tmp-2)for i in range(D):base[i][D-1]=N-Mtmp=0for i in range(M):tmp+=K[i]-1for j in range(D):if j!=tmp+1:base[tmp][j]=0tmp+=2base=my_pow(base,L,MOD)ans=pow(N,L,MOD)for i in range(D):if i not in s:ans-=base[D-1][i]print((ans%MOD+MOD)%MOD)