CF914G Sum the Fibonacci

CodeForces

Luogu

分析

设 $cnt[i]$ 表示 $i$ 的个数。

那么原式可以视为 $cnt[s_a|s_b]\times f(s_a|s_b)$ 、$cnt[s_c]\times f(s_c)$ 、$cnt[s_d\hat\ s_e]\times f(s_d\hat\ s_e)$ 的与卷积。

先不考虑 $f()$ ,那么第一个式子可以子集卷积做,第二个式子不用管,第三个式子可以异或卷积做。

然后求出来后再乘上对应位置的 $f$ 。

接着做一次与卷积,把三个东西乘到一起去,把所有 $2^i$ 位置的答案加起来就行了。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
#define popcount __builtin_popcount
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=300000+10;
const int mod=1e9+7,inv2=500000004;
inline void add(int& x,int y) { x=(x+y)%mod; }
inline void mul(int& x,int y) { x=1ll*x*y%mod; }

inline void FWTor(int* A,int n,int op) {
    for (re int i=1;i<n;i<<=1)
        for (re int j=0;j<n;j+=(i<<1))
            for (re int k=0;k<i;++k)
                add(A[j+k+i],(A[j+k]*op+mod)%mod);
}

inline void FWTand(int* A,int n,int op) {
    for (re int i=1;i<n;i<<=1)
        for (re int j=0;j<n;j+=(i<<1))
            for (re int k=0;k<i;++k)
                add(A[j+k],(A[j+k+i]*op+mod)%mod);
}

inline void FWTxor(int* A,int n,int op) {
    for (re int i=1;i<n;i<<=1)
        for (re int j=0;j<n;j+=(i<<1))
            for (re int k=0;k<i;++k) {
                int x=A[j+k],y=A[j+k+i];
                A[j+k]=(x+y)%mod,A[j+k+i]=(x-y+mod)%mod;
                if (op==-1) mul(A[j+k],inv2),mul(A[j+k+i],inv2);
            }
}

int cnt[N],tmp[N],f[N];
int A[N],B[N],C[N],F[18][N];

int main() {
    int n=read(),lim=1<<17;
    for (re int i=1;i<=n;++i) {
        int x=read(); ++cnt[x];
        ++F[popcount(x)][x];
    }
    
    for (re int i=0;i<=17;++i) FWTor(F[i],lim,1);
    for (re int i=0;i<=17;++i) {
        memset(tmp,0,sizeof(tmp));
        for (re int j=0;j<=i;++j)
            for (re int k=0;k<lim;++k)
                add(tmp[k],1ll*F[j][k]*F[i-j][k]%mod);
        FWTor(tmp,lim,-1);
        for (re int k=0;k<lim;++k)
            if (popcount(k)==i) A[k]=tmp[k];
    }

    for (re int i=0;i<lim;++i) B[i]=cnt[i];
    FWTxor(B,lim,1);
    for (re int i=0;i<lim;++i) B[i]=1ll*B[i]*B[i]%mod;
    FWTxor(B,lim,-1);

    f[1]=1;
    for (re int i=2;i<lim;++i) f[i]=(f[i-1]+f[i-2])%mod;

    for (re int i=0;i<lim;++i) C[i]=cnt[i];
    for (re int i=0;i<lim;++i) {
        A[i]=1ll*A[i]*f[i]%mod;
        B[i]=1ll*B[i]*f[i]%mod;
        C[i]=1ll*C[i]*f[i]%mod;
    }
    FWTand(A,lim,1),FWTand(B,lim,1),FWTand(C,lim,1);
    for (re int i=0;i<lim;++i)
        A[i]=1ll*A[i]*B[i]%mod*C[i]%mod;
    FWTand(A,lim,-1);

    int ans=0;
    for (re int i=1;i<lim;i<<=1) add(ans,A[i]);
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 09 月 26 日 01 : 42 PM

2 条评论

  1. Siyuan

    当场抓获正在切题的野生 M_sea!

    1. M_sea
      @Siyuan

      呜嘤

发表评论