Quiz

AC code

DP表の定義

// i円玉まで使って
// j円以下を作る方法
ll dp[10][100100];

j円「以下」というところがポイント

DP表の図示

f:id:peroon:20200313224716p:plain

解法

M円を111111で割った値をM'として、M'円「以下」を新1～9円玉で支払う問題になる
M'円との差分は旧1円玉で支払う

コインDP

検索しやすいように名前をつけておこう
コインDPと呼ぼう
今回使った新1～9円玉は代わりに「3円玉、7円玉、10円玉、17円玉」などの設定になっても大丈夫

code 抜粋

// i円玉まで使って
// j円以下を作る方法
ll dp[10][100100];

void prepare(){

  rep(i,10){
    rep(j,100100){
      dp[i][j]=-1;
    }
  }

  dp[0][0] = 1;

  // 1円のみで作る
  rep(j, 100000){
    dp[1][j] = j+1;
  }
  
  // 0円の払い方は1通り
  rep(i,10){
    dp[i][0] = 1;
  }

  FOR(i, 2, 10){
    // i円玉を使う

    // j円払う
    // 上からお下がりのぶん
    FOR(j, 0, 100000){
      dp[i][j] = dp[i-1][j];
    }

    // 累積していくぶん
    FOR(j, 0, 100000){
      dp[i][j+i] += dp[i][j];
      dp[i][j+i] %= mod;
    }
  }
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll Q;cin>>Q;

    prepare();

    while(Q--){
      ll m;cin>>m;
      m /= 111111;
      
      // ll ans = dp[9][m] - dp[9][m-1]; // m円ぴったり払うならこっちのはず
      // ans %= mod;
      // if(ans<0) ans += mod;
      ll ans = dp[9][m];
      p(ans);
    }

    return 0;
}