mayoko’s diary

プロコンとかいろいろ。

SRM 487 div1 hard: BunnySequence

解法

この問題は typical DP contest の準急に非常に似ています(というかこれが元ネタかな?)。

ある数 x について, g(x) がどうなるか, と考えるのではなく, 逆に考えます。1 から逆順に作れる数を辿って行って, どれだけの数を作れるか, と考えます。逆順にたどるということは, ある数 x からは m*x または x-1 が生成されることになりますが m*x という値は任意の x について直前の数としてありえるのに対して, x-1 というのはありえない場合があります。x = m*y+1 という形になっている場合 ,直前の数が x-1 = m*y であったとすると, x-1 は m の倍数なので, f(x-1) = y とならないとおかしいです。つまり, x = m*y+1 という値では, 直前の数としては m*x しかありえないです。

typical DP contest の準急における「駅に止まる」という動作が, この問題では「x -> x-1 とする」という動作に対応します。1 度 1 -> m と変換すると, あとは m 回連続で「x -> x-1 とする」という動作を繰り返してはいけないという条件の下で, どれだけの数を生成できるか, という問題になります。

準急の解法については, 診断人さんがとてもわかりやすい解説を書いているので, そちらを参考にしましょう。
shindannin.hatenadiary.com

const ll MOD = 1e9+9;

class BunnySequence {
public:
    int getNumber(int m, int n) {
        vector<ll> dp(n+10), ng(n+m+10);
        dp[0] = 1;
        dp[1] = 1;
        ng[m] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = (2*dp[i-1]+MOD-ng[i]) % MOD;
            ng[i+m] = dp[i-1];
        }
        return (int)(dp[n]);
    }
};