mayoko’s diary

プロコンとかいろいろ。

AtCoder Regular Contest 037 D - Chaotic Polygons

良い問題だなぁ。TopCoderのMedに出題されそう。

問題:D: Chaotic Polygons - AtCoder Regular Contest 037 | AtCoder

解法:kmjpさんの解法(AtCoder ARC #037 : D - Chaotic Polygons - kmjp's blog)を参考にしました。A_i, B_i, C_iの定義の仕方は同じです。
とりあえず場合分けを書いてみました。f:id:mayokoex:20150419094129j:plain
以下ソースコード

const ll MOD = 1e9+7;
const int MAXL = 100010;

ll dp[MAXL][3];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int L;
    cin >> L;
    dp[0][0] = dp[0][1] = dp[0][2] = 1;
    for (int i = 0; i < L; i++) {
        ll p0 = dp[i][0], p1 = dp[i][1], p2 = dp[i][2];
        ll t = p1+p2;

        dp[i+1][0] += 3*p0+(t*t%MOD)*t;
        dp[i+1][0] %= MOD;

        dp[i+1][1] += 2*p1*p1%MOD*p2;
        dp[i+1][1] += p2*p2%MOD*p1;
        dp[i+1][1] %= MOD;

        dp[i+1][2] += p2*p2%MOD*p2;
        dp[i+1][2] += p1*p2%MOD*p2;
        dp[i+1][2] += t*t;
        dp[i+1][2] += p2*p2%MOD*p1;
        dp[i+1][2] %= MOD;
    }
    cout << dp[L][0] << endl;
    return 0;
}