yukicoder : No.137 貯金箱の焦り

No.42 貯金箱の溜息の解説見て、「こんなん思いつかないよ。幸いコイン同士の価値の比が整数倍だからどうにかなった。これが整数倍じゃなかったらどうなるんだ」と思ったら、ほんとに出てきちゃった。
http://yukicoder.me/problems/192

問題

A[i]円の価値を持つN種類のコインがそれぞれ無限の枚数ある。
各種類の価値は異なることが保証される。

M円を払うコインの組み合わせを答えよ。

解法

自力では解けなかったので、Writer解説及び想定解コードを参考にした。

Mの下のbitから合わせていくことを考える。
pビット目を合わせる時、を0回または1回使って生成できる金額の組み合わせ数は簡単なDPで解ける。
合計金額が円となる組み合わせを以下dp[p][s]とする。

dp[p][s]が求まったら、sの最下位ビットがMのpビット目と一致しているsについて、dp[p+1][s/2]=dp[p][s]で状態を更新する(繰り上げ分を考慮する)。
(p+1)ビット目の処理を行うときは、この繰り上げ分をもとにまたを0回または1回使って生成できる金額の組み合わせ数を求めていく。

各pについて上記DPを行ったら、dp[log(M)][0]が答え。
下記コードでは１次元配列dpを使いまわしており、[p]を省略している。

ll N,M;
ll A[55],dp[50005];
ll mo=1234567891LL;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) cin>>A[i];
	
	dp[0]=1;
	while(M) {
		FOR(i,N) for(x=50000;x>=A[i];x--) (dp[x]+=dp[x-A[i]])%=mo;
		
		FOR(x,25001) dp[x]=dp[x*2+M%2];
		FOR(x,25001) dp[x+25000]=0;
		M/=2;
	}
	
	cout<<dp[0]<<endl;
}

まとめ

No.42が★５ならこっちも★５では…。
最初行列累乗かと思ったけど、O((maxA)^3*M)な訳はないよなーと思った。