Given an integer k and a number of bits b (1 ≤ b ≤ 128), calculate the total number of 1 bits in the binary representations of multiples of k between 0 and 2^b − 1 (inclusive), modulo 1,000,000,009. Input The input will consist of two integers k and b on a single line, with 1 ≤ k ≤ 1000 and 1 ≤ b ≤ 128. Output Write your result as an integer on a single line.

Sample Input and Output

1 4

32

10 5

8

100 7

3

3 28

252698795

11 128

856188165

1 26

872415232

876 128

530649653

题目链接：

题意：给出两个数k，m。问：在0-2^m-1中，为k的倍数的数字的二进制中，总共有多少个1；如k=2 ，m=3时，在0-2^3-1中为二的倍数有10，110,100，所以一共有4个1；即此时答案为4。

解题思路：很明显是数位dp的题目，我们先定义某种状态dp【pos】【k】，状态意为：当前数位为pos，mod k（k为输入的那个）的余数，然后用结构体来记录当前状态有多少个符合的数字count（即被k整除），ans记录这些数字二进制总共有多少个1.

#include
     
      using namespace std;typedef long long ll;const ll mod=1e9+9;int p,k;struct st{	int count;//记录符合数字的个数	ll ans;//记录所需的答案	st():count(-1),ans(0){}	st(int count,ll ans):count(count),ans(ans){}}dp[150][1005];st dfs(int pos,int tem,bool limit){	if(pos==-1){		//cout<
      
       <<" "<
       
        <