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