結果
問題 | No.663 セルオートマトンの逆操作 |
ユーザー |
![]() |
提出日時 | 2018-03-09 23:21:20 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 2,143 bytes |
コンパイル時間 | 1,605 ms |
コンパイル使用メモリ | 172,928 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-10-10 19:27:09 |
合計ジャッジ時間 | 2,563 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 29 |
ソースコード
#include<bits/stdc++.h> using namespace std; using Int = long long; template<typename T> vector<T> make_v(size_t a){return vector<T>(a);} template<typename T> vector<vector<T> > make_v(size_t a,size_t b){ return vector<vector<T> >(a,make_v<T>(b)); } template<typename T> vector<vector<vector<T> > > make_v(size_t a,size_t b,size_t c){ return vector<vector<vector<T> > > (a,make_v<T>(b,c)); } template<typename T> vector<vector<vector<vector<T> > > > make_v(size_t a,size_t b,size_t c,size_t d){ return vector<vector<vector<vector<T> > > > (a,make_v<T>(b,c,d)); } template<typename T> vector<vector<vector<vector<vector<T> > > > > make_v(size_t a,size_t b,size_t c,size_t d,size_t e){ return vector<vector<vector<vector<vector<T> > > > >(a,make_v<T>(b,c,d,e)); } template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type fill_v(T &t,const V &v){t=v;} template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type fill_v(T &t,const V &v){ for(auto &e:t) fill_v(e,v); } //INSERT ABOVE HERE signed main(){ Int n; cin>>n; vector<Int> e(n); for(Int i=0;i<n;i++) cin>>e[i]; auto dp=make_v<Int>(2,2,2,2,n+1); fill_v(dp,0); for(Int a=0;a<2;a++) for(Int b=0;b<2;b++) dp[a][b][a][b][1]=1; auto calc=[](Int x,Int y,Int z){ if(x==0&&y==0&&z==0) return 0; if(x==0&&y==0&&z==1) return 1; if(x==0&&y==1&&z==0) return 1; if(x==0&&y==1&&z==1) return 1; if(x==1&&y==0&&z==0) return 0; if(x==1&&y==0&&z==1) return 1; if(x==1&&y==1&&z==0) return 1; if(x==1&&y==1&&z==1) return 0; return 0; }; Int ans=0; const Int MOD= 1e9+7; for(Int i=1;i<n;i++){ for(Int a=0;a<2;a++){ for(Int b=0;b<2;b++){ for(Int c=0;c<2;c++){ for(Int d=0;d<2;d++){ for(Int x=0;x<2;x++){ if(calc(c,d,x)!=e[i]) continue; if(i+1==n){ if(x!=a||calc(d,a,b)!=e[0]) continue; //cout<<a<<" "<<b<<" "<<c<<" "<<d<<":"<<dp[a][b][c][d][i]<<endl; ans+=dp[a][b][c][d][i]; ans%=MOD; }else{ dp[a][b][d][x][i+1]+=dp[a][b][c][d][i]; dp[a][b][d][x][i+1]%=MOD; } } } } } } } cout<<ans<<endl; return 0; }