原题P6962

目前 $n<=45$ 的部分测试过，没问题，应该是剩余部分WA掉了

我的代码：

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N=100;
int n;
ull s;
ull b[N+5];
ull exgcd(ull &x,ull &y,ull a,ull b)
{
    if(b==0)
    {
        x=1,y=0;
        return a;
    }
    ull g=exgcd(y,x,b,a%b);
    y=y-(a/b)*x;
    return g;
}
int ed;
unordered_map<ull,string> mp;
char str[N+5];
void dfs1(int step,ull sum)
{
    if(step>ed)
    {
        mp[sum]=str;
        return;
    }
    str[step-1]='0';
    dfs1(step+1,sum);
    str[step-1]='1';
    dfs1(step+1,sum+b[step]);
}
void dfs2(int step,ull sum)
{
    if(step>n)
    {
        if(mp.count(s-sum))
        {
            cout<<mp[s-sum];
            cout<<str;
            cout<<"\n";
            exit(0);
        }
        return;
    }
    str[step-ed-1]='0';
    dfs2(step+1,sum);
    str[step-ed-1]='1';
    dfs2(step+1,sum+b[step]);
}
void solve1()
{
    ed=(n+1)/2;
    str[ed]='\0';
    dfs1(1,0);
    str[n-ed]='\0';
    dfs2(ed+1,0);
}
ull a[N+5];
ull A[N+5],S;
bool ans[N+5];
void check(ull ny)//这里检测枚举到的r在模2^64时的逆元是否正确，正确输出答案，否则继续枚举
{
	S=s*ny;
    for(int i=n;i>=1;i--)
    {
        A[i]=b[i]*ny;
        if(S>=A[i])
        {
            S-=A[i];
            ans[i]=1;
        }
    }
    if(S!=0) return;
    for(int i=1;i<=n;i++) cout<<ans[i];
    exit(0);
}
void solve2()
{
    ull k=0;
    ull p=b[1];
    while(p%2==0) ++k,p/=2;
    ull q=0,d=0,g;
    ull pw=1ull<<(64-n);
    ull mx=-1;
    ull r=0;
    ull res1=1ull<<k,res2=1ull<<(64-k);
    g=exgcd(q,d,p,res2);
    for(a[1]=res1;a[1]<=pw;a[1]+=2*res1)
    {
        r=a[1]/res1*q;
        for(d=1;d<=res1;d++)
        {
            ull ny=r+d*res2;
            check(ny);
        }
    }
}
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>b[i];
    }
    cin>>s;
    if(n<=45)
    {
        solve1();
    }
    else
    {
        solve2();
    }
    return 0;
}