数位dp D - Count The Bits

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int mod = 1000000009;
ll dp[130][1010][130]; //dp[i][j][k] 其中i代表第i位，j代表这个数的大小，因为我是要k的倍数，所以对k进行取膜即可，k就是表示这数化成二进制含有1的个数
int k, b;

ll dfs(int pos,int num,int sum,bool limit)
{
	if (pos == -1) return num ? 0 : sum;
	if (!limit&&dp[pos][num][sum] != -1) return dp[pos][num][sum];
	ll ans = 0;
	for(int i=0;i<=1;i++)
	{
		ans += dfs(pos - 1, (num * 2 + i) % k, sum + i, limit&&i);
		ans %= mod;
	}
	if (!limit) dp[pos][num][sum] = ans;
	return ans;
}

ll solve()
{
	return dfs(b - 1, 0, 0, true);
}

int main()
{
	scanf("%d%d", &k, &b);
	memset(dp, -1, sizeof(dp));
	printf("%I64d\n", solve());
	return 0;
}