https://codeforc.es/gym/101982
给定k,b两个数，求在0到2^b-1区间中是k的倍数的数的二进制数中1的个数的总和。
dp。
d[i][j]表示：前二进制长度为i的数中模k为j的数的二进制数里1的个数的总和。（所以最终答案就是d[b][0]）
f[i][j]表示： 前二进制长度为i的数中模k为j的数的个数。
转移：
d[i][j]=d[i-1][j]+d[i-1][j-2^(i-1)%k]+f[i-1][j-2^(i-1)%k]
f[i][j]=f[i-1][j]+f[i-1][j-2^(i-1)%k];
代码：（来自ccsu_cat，使用了滚动数组优化）
1 #include<bits/stdc++.h> 2 #define ll long long 3 using namespace std; 4 const int maxn = 1010, mod = 1e9 + 9; 5 ll d[2][maxn] ,f[130][maxn]; 6 void add(ll &x, ll y) { 7 x = (x + y) % mod; 8 } 9 int gao(int x) { 10 if (!x) 11 return 0; 12 return gao(x / 2) + (x % 2); 13 } 14 int main () { 15 int n, k, p = 1, m = 1, s = 1, cur = 0; 16 cin>>k>>n; 17 for (m = 1; m < k && s < n; m <<= 1) 18 p = p * 2 % k, s++; 19 for (int i = 0; i < m && (i < (1 << s)); i++) { 20 d[cur][i % k] += gao(i); 21 f[cur][i % k]++; 22 } 23 for (int i = s; i <= n; i++) { 24 cur = !cur; 25 for (int j = 0; j < k; j++) { 26 d[cur][j] = d[!cur][j]; 27 int q = (j - p + k) % k; 28 add(d[cur][j], d[!cur][q] + f[!cur][q]); 29 f[cur][j] = f[!cur][j]; 30 add(f[cur][j], f[!cur][q]); 31 } 32 p = p * 2 % k; 33 } 34 cout<<d[cur][0]; 35 }
2018-2019 ACM-ICPC Pacific Northwest Regional Contest (Div. 1) D题（dp）
原文：https://www.cnblogs.com/ccsu-kid/p/11135201.html