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
题目链接：https://codeforces.com/gym/101982/attachments
题意：给出两个数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<bits/stdc++.h>
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<<count<<" "<<tem<<endl;
if(tem==0){
return st(1,0);
}
return st(0,0);
}
if(dp[pos][tem].count!=-1&&!limit){
return dp[pos][tem];
}
st ans;
ans.count=0;//这里不要忘了赋值为零，因为初始值为-1
int up=1;
for(int i=0;i<=up;i++){
st tem1=dfs(pos-1,(tem*2+i)%k,i==up&&limit);
ans.count=(ans.count+tem1.count)%mod;//状态转移
ans.ans=(ans.ans+i*tem1.count+tem1.ans)%mod;///状态转移
}
if(!limit)dp[pos][tem]=ans;
return ans;
}
int main(){
scanf("%d%d",&k,&p);
cout<<dfs(p-1,0,true).ans<<endl;
return 0;
}