結果
問題 |
No.663 セルオートマトンの逆操作
|
ユーザー |
![]() |
提出日時 | 2022-04-11 10:59:09 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 76 ms / 2,000 ms |
コード長 | 1,367 bytes |
コンパイル時間 | 222 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 11,136 KB |
最終ジャッジ日時 | 2024-12-15 06:37:42 |
合計ジャッジ時間 | 2,154 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 29 |
ソースコード
import sys readline=sys.stdin.readline N=int(readline()) E=[int(readline()) for i in range(N)] mod=10**9+7 dp=[[0]*4 for i in range(4)] for i in range(2): for j in range(2): for k in range(2): if (i,j,k)==(1,1,1) or (j,k)==(0,0): e=0 else: e=1 if E[1]==e: dp[i*2+j][j*2+k]+=1 for e in E[2:-1]: prev=dp dp=[[0]*4 for i in range(4)] for i in range(4): for j in range(2): for k in range(2): for l in range(2): if (j,k,l)==(1,1,1) or (k,l)==(0,0): ee=0 else: ee=1 if e==ee: dp[i][k*2+l]+=prev[i][j*2+k] dp[i][k*2+l]%=mod for i in range(2): for j in range(2): for k in range(2): for l in range(2): if (k,l,i)==(1,1,1) or (l,i)==(0,0): e=0 else: e=1 if E[-1]!=e: dp[i*2+j][k*2+l]=0 if (l,i,j)==(1,1,1) or (i,j)==(0,0): e=0 else: e=1 if E[0]!=e: dp[i*2+j][k*2+l]=0 ans=sum(dp[i][j] for i in range(4) for j in range(4))%mod print(ans)