VN_ZR_I - Số không (I)
Tác giả: happyboy99x
Ngôn ngữ: C++
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
long long f[32][32][2][2];
int g[32][2][2];
int n;
int k;
int G(int bit, int smaller, int started) {
if (bit == -1) return started;
int &res = g[bit][smaller][started];
if (res != -1) return res;
res = G(bit - 1, smaller | (n >> bit & 1), started);
if (smaller == 1 || (n >> bit & 1) == 1) {
res += G(bit - 1, smaller, 1);
}
return res;
}
long long F(int bit, int fromLastZero, int smaller, int started) {
if (bit == -1) return 0;
long long &res = f[bit][fromLastZero][smaller][started];
if (res != -1) return res;
res = F(bit - 1, started == 1 ? (fromLastZero + 1) % k : 0, smaller | (n >> bit & 1), started)
+ (started == 1 && fromLastZero == 0 ? G(bit - 1, smaller | (n >> bit & 1), started) : 0);
if (smaller == 1 || (n >> bit & 1) == 1) {
res += F(bit - 1, fromLastZero, smaller, 1);
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
while (cin >> n >> k) {
memset(f, -1, sizeof f);
memset(g, -1, sizeof g);
printf("%lld\n", F(31, 0, 0, 0));
}
return 0;
}