题目链接：codeforces 850E

翻译：luogu

读题是第一要务（大选这么随便真的好吗）

其实答案问你的就是在所有选民心中支持的人的所有情况中，能让一个人连赢两场的情况数是多少

我们假设\(A\)赢了\(B\)和\(C\)，最后将答案\(\times 3\)即可

再记\(A\)赢\(B\)时的\(01\)串为\(S_1\)，\(A\)赢\(C\)时的\(01\)串为\(S_2\)，那么对于这两个串的第\(i\)位与该选民的支持情况的对应有如下\(4\)种情况

1）\((0,0)\)，此时有两种可能\(BCA,CBA\)

2）\((0,1)\)，只有一种情况\(BAC\)

3）\((1,0)\)，\(CAB\)

4）\((1,1)\)，\(ABC\)或\(ACB\)

这意味着对于\(S_1\)和\(S_2\)中相同的位上对答案有\(\times 2\)的贡献，记其不同的位为\(cnt\)，则此时的答案为\(2^{n-cnt}\)

为什么记不同的呢？因为不同的数量我们可以直接\(xor\)搞一下

还要考虑\(A\)连胜两场呢？这不就对应着两次函数\(f\)的值的乘积为\(1\)吗

于是把题目中的\(f\)数组做一下\(xor\)卷积，每一位对答案的贡献就是\(2^{n-cnt_i}*p_i\)（\(p_i\)表示卷积之后的数组的值）

#include<iostream>

#include<string.h>

#include<string>

#include<stdio.h>

#include<algorithm>

#include<math.h>

#include<vector>

#include<queue>

#include<map>

using namespace std;

const int maxd=1000000007,N=100000,inv2=500000004;

const double pi=acos(-1.0);

typedef long long ll;

int n,cnt[1100000];

ll bin[1100000],a[1100000],b[1100000];

char s[1100000];

int read()

{

    int x=0,f=1;char ch=getchar();

    while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}

    while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}

    return x*f;

}

void fwt(int lim,ll *a,int typ)

{

    int mid;

    for (mid=1;mid<lim;mid<<=1)

    {

        int len=(mid<<1),sta,j;

        for (sta=0;sta<lim;sta+=len)

        {

            for (j=0;j<mid;j++)

            {

                int x=a[sta+j],y=a[sta+j+mid];

                a[sta+j]=(x+y)%maxd;

                a[sta+j+mid]=(x-y+maxd)%maxd;

                if (typ==-1)

                    {a[sta+j]=(a[sta+j]*inv2)%maxd;a[sta+j+mid]=(a[sta+j+mid]*inv2)%maxd;}

            }

        }

    }

}

int main()

{

    n=read();int lim=(1<<n),i;

    scanf("%s",s);bin[0]=1;

    for (i=0;i<lim;i++) {a[i]=s[i]-'0';b[i]=a[i];}

    for (i=1;i<lim;i++) {bin[i]=(bin[i-1]<<1)%maxd;cnt[i]=cnt[i>>1]+(i&1);}

    fwt(lim,a,1);fwt(lim,b,1);

    for (i=0;i<lim;i++) a[i]=(a[i]*b[i])%maxd;

    fwt(lim,a,-1);

    ll ans=0;

    for (i=0;i<lim;i++) ans=((a[i]*bin[n-cnt[i]])%maxd+ans)%maxd;

    ans=(ans*3)%maxd;

    printf("%lld",ans);

    return 0;

}