P6962 [NEERC2017]Knapsack Cryptosystem

· · 题解

题意

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

$$(\sum_{i=1}^{k-1}a_i)< a_k\quad \text{性质1}$$ $$\sum a_i< 2^{64}\quad\text{性质2}$$ 再随机一个 $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 时取到最优复杂度。