Typical DP Contest E - 数

問題文 : 数

解法 :
$dp[i][j] :=$ 桁$i$ までの和 mod $D$ が$j$ になるものの総数, としてDP. ここで, DP をしている時の数字が上限$L$ に引っかかっていないかを状態として持つと楽.

コード :

#include <cstdio>
#include <cstring>

using namespace std;

int MOD = 1000000007;

char P[10001];
int dp[10001][100][2];
int L, D;

int count(int pos, int mod, bool free)
{
	if (pos == L) return (mod == 0);
	if (dp[pos][mod][free] >= 0) return (dp[pos][mod][free]);
	
	int ret = 0;
	for (int i = 0; i <= (free ? 9 : P[pos] - '0'); i++){
		ret = (ret + count(pos + 1, (mod + i) % D, free | (i < P[pos] - '0'))) % MOD;
	}
	
	return (dp[pos][mod][free] = ret);
}

int main()
{
	memset(dp, -1, sizeof(dp));
	scanf("%d", &D);
	scanf("%s", P);
	
	L = strlen(P);
	
	printf("%d\n", (count(0, 0, 0) + MOD - 1) % MOD);
}