Codeforces431D Random Task

题意:输入n,k,找一个区间[n+1, n*2],使得这个区间里面有m个数二进制有k个1,输出n
题解:
数位dp+二分,这里证明一下单调性,可以发现:
sum(n+1, 2*n)个数为m
sum(n+2, 2*n+2) = sum(n+1, 2*n)+sum(2*n+1, 2*n+1)+sum(2*n+2, 2*n+2)-sum(n+1, n+1)
因为sum(2*n+2, 2*n+2) == sum(n+1, n+1)
非严格单调递增
接下来就是数位dp了,数位dp套模板,dp[i][j]代表前i位有j个1的个数
dfs(int pos,int num, int limit),这里不用考虑前导0,无影响

#include <iostream>
#include <stdio.h>
#include <string.h>
#define maxn 1001000
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;
ll dp[65][65], a[65], k, m;
ll dfs(ll pos, ll num, bool limit){
    if(pos == -1) return num==k;
    if(!limit && dp[pos][num] != -1) return dp[pos][num];
    ll t = limit?a[pos]:1;
    ll ans = 0;
    for(ll i=0;i<=t;i++){
        ans += dfs(pos-1, num+i, limit&&(i==a[pos]));
    }
    if(!limit) dp[pos][num] = ans;
    return ans;
}
ll solve(ll x){
    ll pos = 0;
    while(x){
        a[pos++] = x%2;
        x /= 2;
    }
    return dfs(pos-1, 0, true);
}
int main(){
    memset(dp, -1, sizeof(dp));
    scanf("%lld%lld", &m, &k);
    ll l = 1, r = 1e18, ans = -1;
    while(l<=r){
        ll mid = (l+r)>>1;
        //cout<<l<<" "<<r<<endl;
        if(solve(mid*2)-solve(mid) < m) l = mid+1;
        else r = mid-1, ans = mid;
    }
    printf("%lld
", ans);
    return 0;
}