题面

给定整数m,km,km,k，求出最小和最大的正整数 nnn 使得 n+1,n+2,…,2nn+1,n+2,…,2nn+1,n+2,…,2n 中恰好有 mmm 个数在二进制下恰好有 kkk 个 111。如果有无数个满足条件则输出一行一个整数−1-1−1。有TTT组数据。

T≤2000T\le 2000T≤2000

m≤1e18m\le 1e18m≤1e18

k≤64k\le 64k≤64

保证1e181e181e18内存在一个数满足条件。

题解

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

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

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

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

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\n", l, L-1);

		}

	}

}

巴特西

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

题面

题解

CODE

最新文章

热门文章