自动搬运

查看原文

来自洛谷，原作者为

	oisdoaiu 林地生长于漫宿墙外。每一个研习诸史的人都知道，漫宿无墙

搬运于2025-08-24 22:25:29，当前版本为作者最后更新于2021-03-16 15:04:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

给 $n$ 个物品，每个物品只有 $1$ 个，体积为 $b_i$，求取出物品总体积为 $s$ 的方案。(模 $2^{64}$，保证有且仅有一个解)

$b_i$ 的生成方式为：随机一个长度为 $n$ 的 $a_i$ 序列，满足对于任意 $k$ 都有：

再随机一个 $r$，$r<2^{64}$ 且 $r$ 和 $2^{64}$ 互质。然后 $b_i\equiv a_i\cdot r\ (mod\ 2^{64})$ 。

$n\leq64$

Case 1

显然这一个超大背包问题，那么我们学过一个经典的折半的解决方法，复杂度$O(2^{\frac n2})$，可以解决 $n\leq46$ 的部分。

简单讲一下，就是暴力枚举前一半的所有选择方案，用一个数据结构把所有 $(S,sum)$ 存下来，然后再枚举后一半的所有选择方案，看是否存在对应的前一半的选择方案。

inline void Solve(){
    int mid = n>>1, tp = 1<<mid;
    for(register int s=0; s<tp; s++){
        ull sum=0;
        for(register int i=1; i<=mid; i++) if((s>>i-1)&1) sum += b[i];
        insert(sum,s);
    }
    tp = 1<<(n-mid);
    for(register int s=0; s<tp; s++){
        ull sum=0;
        for(register int i=1; i<=n-mid; i++) if((s>>i-1)&1) sum += b[mid+i];
        int ps = find(S-sum);
        if(ps!=-1){
            for(register int i=1; i<=mid; i++) if((ps>>i-1)&1) putchar('1'); else putchar('0');
            for(register int i=1; i<=n-mid; i++) if((s>>i-1)&1) putchar('1'); else putchar('0');
            puts("");
            return;
        }
    }
}

Case 2

考虑 $n\in(46,64]$ 的部分。

注意一下 $b_i$ 的生成方式，如果我们知道了 $r$，那么就可以求出 $a_i$ 和对应的 $s'$。根据 $a_i$ 的性质，可以直接贪心求出答案。

for(register int i=n; i; i--) 
	if(S>=a[i]) S -= a[i], ans[i] = '1';
	else ans[i] = '0';

首先根据性质2，是不用考虑取模的。其次，从大到小考虑时，如果 $S\geq a_k$ 而不选 $a_k$，根据性质1，就算后面全部选也凑不齐 $a_k$，更别说凑齐 $S$ 了。

那么核心问题转为了如何求 $r$。

根据性质1可以推出 $a_1<\frac{2^{64}}{2^n}$，于是得到了 $a_1$ 的范围，$mx=\frac{2^{64}}{2^n}$。又因为 $r$ 是一个奇数，所以 $a_1$ 末尾 $0$ 的个数一定和 $b_1$ 末尾 $0$ 的个数一样，设为 $cnt$，那么可能的 $a_i$ 就只有 $\frac{2^{64}}{2^{n-cnt-1}}$个，大概是 $2^{18}$ 级别。

于是想到枚举 $a_1$，然后求出 $r^{-1}$。也就是求 $a_1\equiv r^{-1}\cdot b_1\ (mod\ 2^{64})$，先同除 $2^{cnt}$，得到 $a'\equiv r^{-1}\cdot b'\ (mod\ 2^{64-cnt})$，此时因为 $b'$ 是奇数与 $2^{64-cnt}$ 互质，所以可以直接用快速幂求出 $b'^{-1}$ 。

ull tp=1ull<<(64-n-cnt-1);
for(register ull i=0; i<tp; i++){
    ull a1 = (((i<<1)|1)<<cnt);
    ull r = (a1>>cnt)*ksm(tmp,(1ull<<(64-cnt-1))-1); 
    if(cnt) r = r&((1ull<<64-cnt)-1);
}

但是这样求出的是模 $2^{64-cnt}$ 意义下的 $r^{-1}$，无法求出真正的 $r^{-1}$ 的开头 $cnt$ 位，所以还要 $2^{cnt}$ 枚举一下。

ull tp1=1ull<<cnt;
for(register ull j=0; j<tp1; j++){
    ull true_r = r|(j<<63-cnt+1);
    check(true_r);
}

杂项

代码

出密码学的都是毒瘤

快速幂部分可以直接使用自然溢出快速幂，因为 $a\mod b=(a\mod kb)\mod b$

关于复杂度，设两个 $Case$ 分界点为 $k$，那么复杂度分别为 $O(2^{\frac k2})$ 和 $O(2^{n-k})$，所以理论上 $k=\frac23\cdot64$ 时取到最优复杂度。