Luogu

Gym

分析

一个做法是直接 meet in the middle，复杂度 $\mathcal{O}(2^{n/2})$，并不能过 $n\leq 64$。

但是题目中还有一个奇妙的性质 $a_i > \sum_{j=1}^{i-1} a_j$，套用得到 $a_1<2^{65-n}$。

发现随着 $n$ 增大 $a_i$ 的取值范围逐渐减小，这启发我们在 $n$ 大时去枚举 $a_1$。

枚举 $a_1$ 后考虑解出 $r^{-1}$，这样子就可以直接求出 $a_{1..n}$，然后倒着贪心一下就可以求出 $s_{1..n}$ 了。

可以列出同余方程
$$
a_1\equiv b_1r^{-1}\pmod{q}
$$
设 $z=v_2(b_1)$，$b'=\frac{b_1}{2^z}$，那么
$$
a_1\equiv2^zb'r^{-1}\pmod{q}
$$
因为 $r$ 是奇数，所以 $v_2(a_1)=z$，设 $a'=\frac{a_1}{2^z}$，那么
$$
a'\equiv b'r^{-1}\pmod{2^{64-z}}
$$
这样子可以解出 $r'=r^{-1}\bmod 2^{64-z}$，$r^{-1}$ 实际取值可能为 $r'+k2^{64-z}(0\leq k<2^z)$。于是我们再枚举 $k$，然后检查得到的 $a_{1..n}$ 是否合法即可。

这样子 $a_1$ 的总枚举量是 $2^{64-n-z}$，$k$ 的总枚举量是 $2^z$，所以总的枚举量是 $2^{64-n}$ 的。

于是我们把两个做法缝合一下，当 $n\leq B$ 时用做法一，否则用做法二，即可做到 $\mathcal{O}(q^{\frac{1}{3}})$。

代码

下面的实现并不是很完美。

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef unsigned long long ull;

const int N=64+10;

int n; ull b[N],s;

namespace Alice {
    vector<ull> x,y;
    map<ull,int> M;
    void main() {
        for (int i=1;i<=n/2;++i) x.emplace_back(b[i]);
        for (int i=n/2+1;i<=n;++i) y.emplace_back(b[i]);
        for (int S=0;S<1<<x.size();++S) {
            ull sum=0;
            for (int i=0;i<x.size();++i)
                if (S&(1<<i)) sum+=x[i];
            M[sum]=S;
        }
        ull ans=0;
        for (int S=0;S<1<<y.size();++S) {
            ull sum=0;
            for (int i=0;i<y.size();++i)
                if (S&(1<<i)) sum+=y[i];
            if (M.count(s-sum)) { ans=M[s-sum]|((ull)S<<x.size()); break; }
        }
        for (int i=1;i<=n;++i) putchar((ans>>(i-1)&1)+'0');
    }
}

namespace Celia {
    ull a[N];

    ull inv(ull b) {
        ull t=b,r=1;
        for (int i=1;i<64;++i)
            if (t&(1ull<<i)) t+=b<<i,r|=1ull<<i;
        return r;
    }

    bool check() {
        ull s=a[1];
        for (int i=2;i<=n;++i) {
            if (a[i]<=s||s+a[i]<=s) return 0;
            s+=a[i];
        }
        return 1;
    }

    void main() {
        int z=__builtin_ctzll(b[1]);
        ull ib=inv(b[1]>>z),ir=ib;
        for (int i=1;i<1<<(65-n-z);i+=2,ir+=ib<<1)
            for (int j=0;j<1<<z;++j,ir+=2ull<<(63-z)) {
                for (int k=1;k<=n;++k) a[k]=b[k]*ir;
                if (check()) {
                    ull ans=0,r=s*ir;
                    for (int k=n;k;--k)
                        if (r>=a[k]) r-=a[k],ans|=1ull<<(k-1);
                    for (int k=1;k<=n;++k) putchar((ans>>(k-1)&1)+'0');
                    return;
                }
            }
    }
}

int main() {
    scanf("%d",&n);
    for (int i=1;i<=n;++i) scanf("%llu",b+i);
    scanf("%llu",&s);
    if (n<=40) Alice::main();
    else Celia::main();
    return 0;
}