yukicoder : No.189 SUPER HAPPY DAY

問題文を勘違いして大幅タイムロス。相変わらず慌てすぎである。
http://yukicoder.me/problems/493

問題文

ある暦では、1年がMか月、1か月がD日ある。
月の各桁を足したものと、日の各桁を足したものが一致する日は1年に何日あるか。

解法

M,Dが10^200と大きいので全列挙は難しいが、桁の和は高々1800である。
桁の和がxになる月の数をm(x)、桁の和がyになる日の数をd(y)を数え上げてしまえば、あとは
で解を求められる。

巨大数M,Dからm(x),d(y)を数え上げるには桁DPを行う。
メモ化再帰等々色んなDP方法があるので以下一例。

先に任意の(leading zeroも含めた)n桁の整数において、各桁の和がmになるような物の数f(n,m)を求めておく。
これは各桁0～9を取るときの総和を求める単純なDPで済む。

次に、Xyyyyyyという形の(n+1)桁の巨大数Mについて、m(x)を求めることを考える。
先頭の桁が0～(X-1)の時、後ろのn桁は0～9の任意の値を取れるので、この部分は先に求めたf(n,m)を用いて総和ごとの組み合わせ数を求められる。
後は先頭の桁0～(X-1)を加えれば、全体の桁の和ごとの組み合わせ数を求められる。

先頭がXの場合、再帰的に残りyyyyyyの部分について桁の総和ごとの組み合わせを求め、最後に桁の総和にXを加えればよい。
最後yyyyyyが0桁になる場合も1通りとカウントすることに注意。

string M,D;
ll mo=1000000009;

map<int,ll> enumdigsum(string S) {
	const int mdig=200;
	static ll dp[mdig+5][mdig*10+50];
	int tot=0,i,x,y;
	map<int,ll> R;
	
	if(dp[0][0]==0) {
		dp[0][0]=1;
		FOR(i,mdig+2) FOR(y,mdig*10+2) FOR(x,10) (dp[i+1][y+x]+=dp[i][y])%=mo;
	}
	
	reverse(S.begin(),S.end());
	while(S.size()) {
		int x=S[S.size()-1]-'0';
		FOR(i,x) FOR(y,mdig*10+2) if(dp[S.size()-1][y]) (R[y+tot+i] += dp[S.size()-1][y])%=mo;
		tot+=x;
		S.pop_back();
	}
	R[tot]++;
	return R;
}

void solve() {
	
	cin>>M>>D;
	map<int,ll> MM = enumdigsum(M);
	map<int,ll> DD = enumdigsum(D);
	
	ll ret=0;
	ITR(it,MM) if(it->first) ret += it->second*DD[it->first]%mo;
	cout<<ret%mo<<endl;
}

まとめ

190のリジャッジ中に、巨大数の各桁の和を数え上げる部分をライブラリにした。