square869120Contest #2 : C - 何通りの分割方法がある？

もう一段階工夫がいるかと思ったらそうでもなかった。
http://s8pc-2.contest.atcoder.jp/tasks/s8pc_2_c

問題

大きな整数Nが与えられる。
この整数を幾つかに区切ったとき、和がD以下となるようにしたい(区切った個々の整数はleading zeroを含んでいても良い)。
区切り方は何通りあるか。

解法

Dは小さいので、
dp(d,sum) := 上位d桁までを区切った場合、和がちょうどsumとなる組み合わせ
を愚直に更新していけば良い。
もうひとひねりいるかと思ったけど、桁数がそこまで大きくないので何とか間に合ってしまった。

int L,D;
string S;
ll dp[105][100005];
ll mo=1000000007;

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>S>>D;
	dp[0][0]=1;
	L=S.size();
	FORR(r,S) r-='0';
	FOR(i,L) {
		ll sum=0;
		for(l=1;i+l<=L;l++) {
			sum=sum*10+S[i+l-1];
			if(sum>D) break;
			for(x=0;x+sum<=D;x++) if(dp[i][x]) {
				dp[i+l][x+sum] += dp[i][x];
				if(dp[i+l][x+sum]>=mo) dp[i+l][x+sum]-=mo;
			}
		}
	}
	ll tot=0;
	FOR(i,D+1) tot+=dp[L][i];
	cout<<tot%mo<<endl;
	
}

まとめ

leading zeroを不許可にしてもいいかと思ったけど、その方がむしろ計算量的には簡単か。
7桁以上の整数取れなくなるしね。