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;
}

Download