OpenJudge

6666

  • 陈昱彤อัััััััััััััััั(;̷̸̨̀͒̏̃ͦ̈́̾̀́̎͢҉̵͚̼͉͖̺̥͔͇̰̹̮͙͉̻̼̭̻͕̮͇ͨͬͪ͗̇̑̽͋̀̋̊͌ͧͨͭ̓̅͐ͥ̂̔̊ͧ͊)
    陈昱彤อัััััััััััััััั(;̷̸̨̀͒̏̃ͦ̈́̾̀́̎͢҉̵͚̼͉͖̺̥͔͇̰̹̮͙͉̻̼̭̻͕̮͇ͨͬͪ͗̇̑̽͋̀̋̊͌ͧͨͭ̓̅͐ͥ̂̔̊ͧ͊) 18.2.4 回复

    #include <iostream>
    #include <vector>
    #include <algorithm>
    #include <cstring>
    #include <cstdio>
    #include <cstdlib>
    #include <cmath>
    #define MOD 1000000007
    #define INF 1e9
    using namespace std;
    typedef long long LL;
    const int MAXN=1010;
    inline int max(int &x,int &y) {return x>y?x:y;}
    inline int min(int &x,int &y) {return x<y?x:y;}
    inline int gi() {
    register int w=0,q=0;register char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')q=1,ch=getchar();
    while(ch>='0'&&ch<='9')w=w*10+ch-'0',ch=getchar();
    return q?-w:w;
    }
    const int __bmod__=100000;
    struct BN{
    int a[100];
    BN(){memset(a,0,sizeof(a));}
    int& operator [](int n){return a[n];}
    void get(int n){
    memset(a,0,sizeof(a));
    a[1]=n;if(a[1])a[0]=1;
    while(a[a[0]+1]){a[a[0]+1]=a[a[0]]/__bmod__;a[a[0]++]%=__bmod__;}
    }
    bool operator <(BN b) const{
    if(a[0]<b[0])return 1;
    if(a[0]>b[0])return 0;
    for(int i=a[0];i>=1;i--){
    if(a[i]>b[i])return 0;
    if(a[i]<b[i])return 1;
    }
    return 0;
    }
    BN operator -(BN b) const{
    BN ans=*this;int q=1;
    if(ans<b)swap(ans,b),q=-1;
    for(int i=1;i<=ans[0];i++){
    ans[i]=ans[i]-b[i];
    if(ans[i]<0){ans[i+1]--;ans[i]+=__bmod__;}
    }
    while(ans[0]&&!ans[ans[0]])ans[0]--;
    for(int i=1;i<=ans[0];i++)ans[i]*=q;
    return ans;
    }
    BN operator +(BN b) const{
    b[0]=max(a[0],b[0]);
    for(int i=1;i<=b[0];i++){
    b[i]+=a[i];
    if(b[i]>=__bmod__){b[i+1]+=b[i]/__bmod__;b[i]%=__bmod__;}
    }
    if(b[b[0]+1])b[0]++;
    return b;
    }
    BN operator *(BN b) const{
    BN ans;
    ans[0]=a[0]+b[0]-1;
    for(int i=1;i<=a[0];i++)
    for(int o=1;o<=b[0];o++){
    int now=i+o-1;
    ans[now]+=a[i]*b[o];
    }
    for(int i=1;i<=ans[0];i++)if(ans[i]>=__bmod__){ans[i+1]+=ans[i]/__bmod__;ans[i]%=__bmod__;}
    if(ans[ans[0]+1])ans[0]++;
    return ans;
    }
    void print(){printf("%d",a[a[0]]);for(int i=a[0]-1;i>=1;i--)printf("%.5d",a[i]);printf("\n");}
    }now,f[2],o,t,up,mu;
    int a[MAXN];
    int main()
    {
    //freopen("1832.in","r",stdin);
    //freopen("1832.out","w",stdout);
    int T=gi();
    while(T--){
    int n=gi();
    for(int x=0;x<2;x++){
    for(int i=n;i>=1;i--)a[i]=gi();
    f[x].get(a[1]),o.get(1-a[1]),t.get(1),up.get(1),mu.get(2);
    for(int i=2;i<=n;i++){
    if(a[i])
    now=f[x],f[x]=o+t+up,o=now;
    else o=o+t+up;
    t=t*mu+up;
    }
    }
    if(f[0]<f[1])
    (f[1]-f[0]).print();
    else (f[0]-f[1]).print();
    }
    return 0;
    }

想要评论吗?

注册OpenJudge账号,如果您已经注册,请先登入