yukicoder No.137 貯金箱の焦り

さっき解いた問題が貯金箱シリーズに似てたのでいけると思った(いけなかった)。貯金箱シリーズ, 上手いこと SRM のバージョンとは差をつけていて, 上手いなぁと思います。

問題

No.137 貯金箱の焦り - yukicoder

解法

「硬貨 A[i] をいくらでも使って良い」というのは, 「硬貨 A[i], 2*A[i], 4*A[i], ..., 2^n * A[i] のそれぞれを 使う/使わない は好きに選んで良い」ということと同じになります。

そこで, まず 1*A[i] シリーズを使って dp[x] = (x 円払う方法の数) というよくある DP をします。この DP では, 各硬貨は 1 枚より多い枚数を使っちゃいけないことに注意です。
この後は 2*A[i] シリーズ, 4*A[i] シリーズ, ... となっていくわけですが, これらの和はどうあがいても必ず 2 の倍数になります。よって, 1*A[i] シリーズを使った時点で M と偶奇が合っていなければ, 絶対に M 円になることはありません。よって, 求めた dp のうち, 半分の情報は捨てていいことになります。
偶奇が一致しない場合をスルーして, 次に 2*A[i] シリーズを考えるわけですが, ここでは上と同様にして, 下から 2 bit 目の bit 値を dp と M で合わせる必要があります。以下同様です。

これをまとめると, dp[p][x] = ((p-1)bit までは M と一致していて, 2^p 以上の値については, 合計が 2^p * x となるような場合の数) という dp を考えれば良いです。

const int MAXN = 55;
const ll MOD = 1234567891;
int A[MAXN];
ll dp[500*101];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    ll M;
    cin >> N >> M;
    for (int i = 0; i < N; i++) cin >> A[i];
    dp[0] = 1;
    while (M) {
        for (int i = 0; i < N; i++) {
            for (int j = 100*500; j >= A[i]; j--) {
                (dp[j] += dp[j-A[i]]) %= MOD;
            }
        }
        for (int i = 0; i <= 50*500; i++) {
            dp[i] = dp[i*2+M%2];
        }
        for (int i = 0; i <= 50*500; i++) {
            dp[i+50*500] = 0;
        }
        M /= 2;
    }
    cout << dp[0] << endl;
    return 0;
}