https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_g
解説
https://atcoder.jp/contests/tkppc4-1/submissions/6664457
制約に弱点がないので、なにか特殊な性質があるのだろうと考察する。
まずは実験してみよう。
ll dp[30];
void labo() {
dp[0] = 0;
dp[1] = 1;
rep(i, 2, 30) {
dp[i] = i;
rep(j, 0, i) chmax(dp[i], dp[j] * dp[i - j]);
}
rep(i, 0, 30) printf("dp[%d] = %lld\n", i, dp[i]);
}
結果は
dp[0] = 0 dp[1] = 1 dp[2] = 2 dp[3] = 3 dp[4] = 4 dp[5] = 6 dp[6] = 9 dp[7] = 12 dp[8] = 18 dp[9] = 27 dp[10] = 36 dp[11] = 54 dp[12] = 81 dp[13] = 108 dp[14] = 162 dp[15] = 243 dp[16] = 324 dp[17] = 486 dp[18] = 729 dp[19] = 972 dp[20] = 1458 dp[21] = 2187 dp[22] = 2916 dp[23] = 4374 dp[24] = 6561 dp[25] = 8748 dp[26] = 13122 dp[27] = 19683 dp[28] = 26244 dp[29] = 39366
これを見ると、なるべく3を作って、余ったら2にする方針みたい。
N % 3 == 0ならば、333...のようにする
N % 3 == 1ならば、2を2つ作る。22333...
N % 3 == 2ならば、2を1つ作る。233*...
あとは、小さいケースにコーナーがあるので気をつけよう。
ll dp[30]; void labo() { dp[0] = 0; dp[1] = 1; rep(i, 2, 30) { dp[i] = i; rep(j, 0, i) chmax(dp[i], dp[j] * dp[i - j]); } rep(i, 0, 30) printf("dp[%d] = %lld\n", i, dp[i]); } //--------------------------------------------------------------------------------------------------- mint solve(ll N) { if (N % 3 == 0) { if (N == 0) return 0; return mint(3) ^ (N / 3); } else if (N % 3 == 1) { if (N == 1) return 1; return mint(2) * mint(2) * (mint(3) ^ ((N - 4) / 3)); } else return mint(2) * (mint(3) ^ ((N - 2) / 3)); } //--------------------------------------------------------------------------------------------------- void _main() { int Q; cin >> Q; rep(q, 0, Q) { ll N; cin >> N; mint ans = solve(N); printf("%d\n", ans.get()); } }
