Submission #5991071

---

Source Code Expand

// {{{
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
// }}}

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;

static constexpr int mod = (int)1e9 + 7;
static constexpr int inf = 100100100;
static constexpr ll linf = 1e18;
static constexpr double eps = 1e-9;
static constexpr double pi = 3.14159265359;

#define rep(i, n) for (ll i = 0; i < n; ++i)
#define rrep(i, n) for (ll i = n; i >= 0; --i)
#define all(c) begin(c), end(c)
#define rall(c) rbegin(c), rend(c)
#define pb push_back
#define ist insert
#define fst first
#define snd second


// {{{
template <typename T>
struct modint {
    static_assert(std::is_integral<T>::value, "T must be integral");
    modint(T value = 0, T mod = (T)1e9 + 7) : value(value % mod), mod(mod) {}
    modint operator +(const modint& rhs) const {
        return modint(*this) += rhs;
    }
    modint operator -(const modint& rhs) const {
        return modint(*this) -= rhs;
    }
    modint operator *(const modint& rhs) const {
        return modint(*this) *= rhs;
    }
    modint operator /(const modint& rhs) const {
        return modint(*this) /= rhs;
    }
    modint& operator +=(const modint& rhs) {
        value += rhs.value;
        if (value >= mod) {
            value -= mod;
        }
        return *this;
    }
    modint& operator -=(const modint& rhs) {
        if (value < rhs.value) {
            value += mod;
        }
        value -= rhs.value;
        return *this;
    }
    modint& operator *=(const modint& rhs) {
        value = value * rhs.value % mod;
        return *this;
    }
    modint& operator /=(const modint& rhs) {
        modint tmp = rhs;
        T exp = mod - 2;
        while (exp) {
            if (exp % 2) {
                *this *= tmp;
            }
            tmp *= tmp;
            exp /= 2;
        }
        return *this;
    }
    bool operator ==(const modint& rhs) const {
        return value == rhs.value;
    }
    bool operator !=(const modint& rhs) const {
        return !(*this == rhs);
    }
    bool operator >(const modint& rhs) const {
        return value > rhs.value;
    }
    bool operator <(const modint& rhs) const {
        return value < rhs.value;
    }
    bool operator >=(const modint& rhs) const {
        return !(*this < rhs);
    }
    bool operator <=(const modint& rhs) const {
        return !(*this > rhs);
    }
    friend ostream& operator <<(ostream &out, const modint& m) {
        out << m.value;
        return out;
    }
    friend istream& operator >>(istream &in,  modint& m) {
        in >> m.value;
        m.value %= m.mod;
        return in;
    }
    T value;
    T mod;
};
// }}}


ll N;
map<string, modint<ll>> memo[101];

bool ok(string last4) {
    rep (i, 4) {
        string t = last4;
        if (i >= 1) {
            t[i - 1] = last4[i];
            t[i] = last4[i - 1];
        }
        if (t.find("AGC") != t.npos) {
            return false;
        }
    }
    return true;
}

modint<ll> dfs(ll cur, string last3) {
    if (memo[cur].count(last3)) {
        return memo[cur][last3];
    }
    if (cur == N) {
        return 1;
    }
    modint<ll> ret = 0;
    for (char c : {'A', 'C', 'G', 'T'}) {
        if (ok(last3 + c)) {
            ret += dfs(cur + 1, last3.substr(1, 2) + c);
        }
    }
    memo[cur][last3] = ret;
    return ret;
}


int main() {
    // cin.tie(0);
    // ios_base::sync_with_stdio(false);
    cin >> N;
    cout << dfs(0, "TTT") << endl;
}

Submission Info

Judge Result