题意:

给你n个数

保证:

a₁<a₂

a₁+a₂<a₃

a₁+a₂+a₃<a₄

......

a₁+...+a_n-1 < a_n

以及a₁ + ... + a_n < q

现在我们选出了一个数字r,保证gcd(r,q)=1

b_i = a_i * r

那么当我们要发送一个长度为n的01信息给某人,我们可以发送一个b_i的对应位置的和(对q取模)过去

例如11 49 100 发送149表示011(但是b数组不保证a数组的性质)

如果q是120的话,发送29表示011

现在选定q = 2^64

现在给你b,给你发送的数字

知道r的人可以自己通过r^-1来求出相应的信息从而得出结论,但你没有r,你也要求出这个信息.

思路:

考虑n<=40的时候

我们分成两部分,每个部分都是20以内的,暴力

然后一个部分怎么选,我们可以利用和的性质去看另一部分是否满足

n>40的时候,我们可以发现

a₁的值应该是很小的,一定在2^25以内

我们可以直接枚举这个值

然后根据 r^-1 * a₁ = i反推出r^-1

r^-1 = i * a₁^-1

但是这样直接得出结论会错,因为如果a₁是2的倍数你就求不出来对应的r^-1

如果a₁这个值是2^k的倍数,那么我们可以求出a₁/2^k的逆元;但是这时候因为i是2^k的倍数

所以我们考虑两边都除以2^k,上述式子就能成立,但是就不是%2^64了而是%2^(64-k)

那么我们应该有2^k个解,我们也分别枚举出来就行

代码:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
unsigned long long b[65];
unsigned long long c[65];
unsigned long long power(unsigned long long x,unsigned long long y)
{
    if (y==0) return 1ull;
    unsigned long long t=power(x,y/2);
    t=t*t;
    if (y%2==1) t=t*x;
    return t;
}
bool over(unsigned long long x,unsigned long long y)
{
    int i;
    for (i=63;i>=0;i--)
    {
        if (((1ull<<i)&x)^((1ull<<i)&y)) continue;
        if ((1ull<<i)&x) return true; else return false;
    }
    return false;
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n;
    cin>>n;
    int i;
    for (i=0;i<n;i++)
    {
        cin>>b[i];
    }
    unsigned long long a;
    cin>>a;
    if (n<=40)
    {
        map<unsigned long long,int> ma;
        int j;
        int t=(n/2);
        for (j=0;j<(1<<t);j++)
        {
            int k;
            unsigned long long cnt=0;
            for (k=0;k<t;k++)
            {
                if ((1<<k)&j) cnt+=b[k];
            }
            ma[cnt]=j;
        }
        int l=n-t;
        for (j=0;j<(1<<l);j++)
        {
            int k;
            unsigned long long cnt=0;
            for (k=0;k<l;k++)
            {
                if ((1<<k)&j) cnt+=b[k+t];
            }
            if (ma.find(a-cnt)!=ma.end())
            {
                int i;
                for (i=0;i<t;i++)
                {
                    if ((1<<i)&ma[a-cnt]) printf("1"); else printf("0");
                }
                for (i=0;i<l;i++)
                {
                    if ((1<<i)&j) printf("1"); else printf("0");
                }
                printf("\n");
            }
        }
    }
    else
    {
        int i;
        unsigned long long val;
        for (i=0;i<64;i++)
        {
            if (b[0]&(1ull<<i))
            {
                val=power(b[0]>>i,(1ull<<63)-1);
                break;
            }
        }
        int temp=i;
        for (i=1;i<(1<<(65-n-temp));i++)
        {
            unsigned long long tt=val*i;
            unsigned long long t2;
            for (t2=0;t2<(1ull<<temp);t2++)
            {
                unsigned long long t=tt^(t2<<(64-temp));
                int j;
                unsigned long long sum=0;
                for (j=0;j<n;j++)
                {
                    c[j]=b[j]*t;
                    if (c[j]<sum) break;
                    if (over(sum,c[j])) break;
                    sum+=c[j];
                }
                if (j!=n) continue;
                a*=t;
                string ans;
                for (j=n-1;j>=0;j--)
                {
                    if (a>=c[j])
                    {
                        a-=c[j];
                        ans="1"+ans;
                    }
                    else
                    {
                        ans="0"+ans;
                    }
                }
                cout<<ans<<endl;
                return 0;
            }
        }
    }
    return 0;
}