No.41 貯金箱の溜息（EASY）

c++ yukicoder

No.41 貯金箱の溜息（EASY） - yukicoder

  • 10^5 くらいの再帰をやろうとして stackoverflow してしまった...。
  • 累積 DP がなんで必要かが一瞬わからなかった。
  • カテゴリ的には座標圧縮も入るのか。確かに。
class SighOfSavingsBoxEasy {
public:
    void solve(void) {
            // Mk/111111LL <= 10^10/10^5 = 10^5 なので再帰でやると stackoveflow する。
            // よって dp でやる必要がある。
            // 111111LL 未満は 1 のコインで払う 1 通りしかないので
            // Mk/111111LL を 1~9 までのコインで払う払い方と考える
            ll MaxM = (ll)1E+10;
            MaxM = MaxM/111111LL;

            // dp[i] := i 円を 1~9 までのコインで払う払い方
            vector<ModInt> dp(MaxM+1, 0);
            dp[0] = 1; // 111111LL 未満の払い方は 1 通り

            // O(10*MaxM) <= 10^6
            for (int j = 1; j <= 9; ++j)
            for (ll i = 0; i < MaxM; ++i)
            {
                if (i+j <= MaxM)
                    dp[i+j] += dp[i];
            }

            // dp2[i] := i 円までを 1~9 のコインで払う払い方
            //
            // これは j 円までを (j < i) 1~9 のコインではらって残りを
            // 本来の 1 円コインで払うという払い方ができるから累積 DP が必要
            //
            vector<ModInt> dp2(MaxM+1, 0);
            dp2[0] = 1;
            for (ll i = 1; i <= MaxM; ++i)
                dp2[i] = dp2[i-1] + dp[i];

            int T;
            cin>>T;
            REP(i,T)
            {
                ll m;
                cin>>m;
                cout<<dp2[m/111111LL]<<endl;
            }
    }
};