CSP模拟赛 number （二分+数位DP）

题面

给定整数$m,k$，求出最小和最大的正整数 $n$ 使得 $n+1,n+2,…,2n$ 中恰好有 $m$ 个数 在二进制下恰好有 $k$ 个 $1$。如果有无数个满足条件则输出一行一个整数$-1$。有$T$组数据。
$Tle 2000$
$mle 1e18$
$kle 64$
保证$1e18$内 存在一个数满足条件。

题解

设$f(i)$表示$i+1,i+2,...,2i$中在二进制下为恰好有$k$个$1$的数的个数。可以证明打表发现$f(i)$是单调不降的。所以就可以二分了。二分后数位$DP$就行了。计算$f(i)$可以用$g(2i)-g(i)$，其中$g(i)$表示$1$到$i$的数中在二进制下恰好有$k$个$1$的数的个数。

因为数位$DP$的数组是可以多次用的，所以时间复杂度是整体两个$log$的，而每次时间复杂度为$O(+Tlog^2(二分上界))$

但是这里的二分上界并不是$1e18$，因为保证最小的$n$在$1e18$内，但是最大的可能超出。所以上界我设的$2^{63}$

输出$-1$的情况只有一种就是$k=1$，在$n=2^p$时满足。

CODE

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
ULL m, f[70][70];
int k, c[70], n;
bool vis[70][70];
ULL dfs(int i, int j, bool fp) {
	if(!fp && vis[i][j]) return f[i][j];
	if(i == 0) return j == 0;
	ULL ans = 0; int mx = fp ? c[i] : 1;
	for(int d = 0; d <= mx; ++d) ans += dfs(i-1, j-d, fp&&d==mx);
	if(!fp) vis[i][j] = 1, f[i][j] = ans;
	return ans;
}
ULL cal(ULL x) {
	for(n=0; x; c[++n]=x&1,x>>=1);
	return dfs(n, k, 1);
}
ULL chk(ULL x) { return cal(2*x) - cal(x); }
int main() {
	int T; scanf("%d", &T); while(T--) {
		scanf("%llu%d", &m, &k);
		if(k == 1) puts("-1");
		else {
			ULL l = 1, r = 1llu<<63, mid;
			while(l < r) {
				mid = (l + r) >> 1;
				if(chk(mid) >= m) r = mid;
				else l = mid+1;
			}
			ULL L = 1, R = 1llu<<63, MID;
			while(L < R) {
				MID = (L + R) >> 1;
				if(chk(MID) > m) R = MID;
				else L = MID+1;
			}
			printf("%llu %llu
", l, L-1);
		}
	}
}