Typical DP Contest E 数

問題

http://tdpc.contest.atcoder.jp/tasks/tdpc_number

方針

桁DP.
dp[pos][sum][sml] := pos桁目まで見たとき、各桁の和modPがsumで、与えられた数より小さいかどうか(sml) であるような数の個数
としてこれを更新すればいい。

ソースコード

const int mod = (int)1e9 + 7;
int d, dp[2][100][2];
string n;

int main(){
	cin >> d >> n;
	int cur = 0, next = 1;
	
	dp[0][0][0] = 1;
	rep(i, n.size()){
		memset(dp[next], 0, sizeof(dp[next]));
		rep(j, d) rep(s, 2) if(dp[cur][j][s]){
			rep(k, 10){
				int ns = s || k < n[i] - '0';
				if(!ns && k > n[i] - '0') continue;
				(dp[next][(j + k) % d][ns] += dp[cur][j][s]) %= mod;
			}
		}
		swap(cur, next);
	}
	int ans = (dp[cur][0][0] + dp[cur][0][1]) % mod;
	cout << (ans + mod - 1) % mod << endl;
	
	return 0;
}