VN_ZR_I - Số không (I)

Tác giả: hieult

Ngôn ngữ: C++

#include<cstdio>
#include<cmath>
#include<math.h>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<sstream>
#include<list>
#define fi first
#define se second
#define PB push_back
#define MP make_pair
#define ep 0.00001
#define oo 111111111
#define mod 790972
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
#define rep(i, n) for(int i = 0; i < n; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, x) memset(a, x, sizeof(a))
#define SZ(a) (int)(a.size())
#define maxn 505
//#define g 9.81
double const PI=4*atan(1.0);

using namespace std;

typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;
typedef long long ll;
int dx[] = {+1, 0, -1, 0};
int dy[] = {0, -1, 0, +1};

void OPEN(){
    freopen("A.in","r",stdin);
    freopen("A.out","w",stdout);
}

typedef long long ll;

#define modun 2

int num, a[100];
ll dp[33][2][2][33];
long long n, m;

ll go(int pos, int less, int zero, int cnt) {
    if (pos < 0){
        if(!cnt) return 0;
        else return (cnt - 1)/ m + 1;
    }
    
    ll &ret = dp[pos][less][zero][cnt];
    if (ret != -1) return ret;

   // cout << pos << " " << less << " " << zero << " " << cnt << endl;

    ret = 0;

    int maxd = less ? 1 : a[pos];
    for (int d = 0; d <= maxd; ++d) {
        ret += go(pos - 1, less | (d < a[pos]), zero | d, cnt + (zero && (!d)));
    }

    return ret;
}

ll howmany(ll A) {
    if (A <= 0) return 0;

    num = 0;
    while (A > 0) {
    a[num++] = A & 1;
    A >>= 1;
    }

    memset(dp, -1, sizeof(dp));
    return go(num - 1, 0, 0, 0);
}

ll solve(ll A, ll B) {
    if (A == 0) {
    if (B == 0) return 1;
    return howmany(B) + 1;
    }
    return howmany(B) - howmany(A - 1);
}


int main(){
    //OPEN();
    while(scanf("%lld %lld", &n, &m) > 0){
        printf("%lld\n", howmany(n));
    }
}

Download