ABC 122 D - We Like AGC
僕はAGC好きですよ、じっくり問題が解けるので
問題のリンク
思考過程
・禁止されたパターンがあるタイプの数えあげDP。EDPCのC。
・禁止された状態は以下の5つ。(Xはワイルドカード)
1. AGC
2. ACG
3. CAG
4. AGXC
5. AXGC
・前の3つまでの文字を量子数に持つdp配列を持っておけばヨシ。
・dp[i][j][k][l] := 長さがi文字であって、3つ前の文字がj、2つ前の文字がk、1つ前までの文字がl、であるような文字列の総数。 文字は数字に変換しておく、A->0、G->1、C->2、T->3。
・基本的に遷移は dp[i+1][k][l][new] += dp[i][j][k][l]。ただし禁止された遷移がある。
・禁止された遷移は、、、(j, k, l) -> (k, l, new) として
1. (X, 0, 1) -> (0, 1, 2)
2. (X, 0, 2) -> (0, 2, 1)
3. (X, 1, 0) -> (1, 0, 2)
4. (0, 1, X) -> (1, X, 2)
5. (0, X, 1) -> (X, 1, 2)
・初期値は基本0で、dp[0][3][3][3] = 1としておく。
・あとは素直に実装
#include <iostream> #include <algorithm> #include <vector> #define rep(i,n) for(int i=0;i<n;++i) #define rep1(i,n) for(int i=1;i<=n;++i) using namespace std; template<class T>bool chmax(T &a, const T &b) { if(a < b){ a = b; return 1; } return 0; } template<class T>bool chmin(T &a, const T &b) { if(a > b){ a = b; return 1; } return 0; } typedef long long ll; const ll MOD=1e+9+7; struct mint{ ll x; mint(ll x=0):x(x%MOD){} mint& operator+=(const mint a){ if((x+=a.x)>=MOD) x-=MOD; return *this; } mint& operator-=(const mint a){ if((x += MOD-a.x)>=MOD) x-=MOD; return *this; } mint& operator*=(const mint a){ (x*=a.x)%=MOD; return *this; } mint operator+(const mint a) const{ mint res(*this); return res+=a; } mint operator-(const mint a) const{ mint res(*this); return res-=a; } mint operator*(const mint a) const{ mint res(*this); return res*=a; } mint pow(ll t) const{ if(!t) return 1; mint a = pow(t>>1); a*=a; if(t&1) a*=*this; return a; } //for prime mod mint inv() const{ return pow(MOD-2); } mint& operator/=(const mint a){ return (*this) *= a.inv(); } mint operator/(const mint a) const{ mint res(*this); return res/=a; } }; int main() { int n; cin >> n; mint dp[110][4][4][4]; rep(i,n+1) rep(j,4) rep(k,4) rep(l,4) dp[i][j][k][l].x = 0; dp[0][3][3][3].x = 1; // dp[i][j][k][l] rep(i,n) rep(j,4) rep(k,4) rep(l,4) rep(m,4) { if(m == 2) { if((k == 0 && l == 1) || (k == 1 && l == 0) || (j == 0 && k == 1) || (j == 0 && l == 1)) continue; } else if(m == 1) { if(k == 0 && l == 2) continue; } dp[i+1][k][l][m] += dp[i][j][k][l]; } mint res; rep(j,4) rep(k,4) rep(l,4) res += dp[n][j][k][l]; cout << res.x << "\n"; return 0; }