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)を参考にしました。の定義の仕方は同じです。
とりあえず場合分けを書いてみました。
以下ソースコード
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; }