結果
問題 | 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])%mod if ans[i*n+k]>=mod: ans[i*n+k]-=mod return ans def my_pow(p,x,n,mod): ans=[0]*(n*n) for i in range(n): ans[i*n+i]=1 while x>0: if x%2==1: ans=mul(ans,p,n,mod) x//=2 p=mul(p,p,n,mod) return ans MOD=10**9+7 L,N,M=map(int,input().split()) if M==0: print(0) exit() K=list(map(int,input().split())) s=set() tmp=0 D=sum(K)+M+1 base=[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]=1 for j in range(K[i]): base[(j+tmp)*D+j+1+tmp]=1 tmp+=K[i]+1 base[(tmp-1)*D+tmp-1]=1 s.add(tmp-2) for i in range(D): base[i*D+D-1]=N-M tmp=0 for i in range(M): tmp+=K[i]-1 for j in range(D): if j!=tmp+1: base[tmp*D+j]=0 tmp+=2 base=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)