CF914G.Sum the Fibonacci

• 题目链接：，

• 前置知识：fwt，子集卷积

  题解

• 按题意模拟，做几次子集卷积和各种fwt。

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define rep(i, s, t) for(int i = s, __ = t; i <= __; ++i)
#define dwn(i, s, t) for(int i = s, __ = t; i >= __; --i)

const int INF = 21474837;
const int MAXN = 100 + (1 << 19);
const int MOD = 1000000007;
using namespace std;
inline int read(int x = 0, int f = 1){
    char ch = getchar();
    for(; !isdigit(ch); ch = getchar())if(ch == '-')f = -1;
    for(; isdigit(ch); ch = getchar())x = ch - '0' + x * 10;
    return x * f;
}
inline void write(int x){
    if(x < 0)putchar('-'), x = -x;
    if(x >= 10)write(x / 10); putchar(x % 10 + '0');
    return ;
}

inline int add(int x, int y){x += y; return x >= MOD ? x - MOD : x;}
inline int sub(int x, int y){x -= y; return x < 0 ? x + MOD : x;}
inline void inc(int &x, int y){x += y, x -= x >= MOD ? MOD : 0; return ;}
inline void dec(int &x, int y){x -= y, x += x < 0 ? MOD : 0; return ;}
inline int mul(int x, int y){return (ll)x * y % MOD;}
inline int fpow(int x, int y, int tmp = 1){
    while(y){if(y & 1)tmp = mul(tmp, x); x = mul(x, x), y >>= 1;} return tmp;
}
inline int inv(int x){return fpow(x, MOD -2);}
inline int die(int x, int y){return (ll)x * inv(y) % MOD;}
int n, lim = 1, a[MAXN], ans, inv2;

void fwt_or(int *u, int tag){
    for(int i = 1; i < lim; i <<= 1)
        for(int j = 0; j < lim; j += i << 1)rep(k, 0, i - 1)
            inc(u[j + k + i], ~tag ? u[j + k] : sub(0, u[j + k]));
    return ;
}

void fwt_and(int *u, int tag){
    for(int i = 1; i < lim; i <<= 1)
        for(int j = 0; j < lim; j += i << 1)rep(k, 0, i - 1)
            inc(u[j + k], ~tag ? u[j + k + i] : sub(0, u[j + k + i]));
    return ;
}

void fwt_xor(int *u,int tag){
    for(int i = 1;i < lim; i <<= 1)
        for(int j = 0; j < lim; j += i << 1)rep(k, 0, i - 1){
            int x = u[j + k], y = u[j + k + i];
            u[j + k] = add(x, y), u[j + k + i] = sub(x, y);
            if(tag == -1){
                u[j + k] = mul(u[j + k], inv2);
                u[j + k + i] = mul(u[j + k + i], inv2);
            }
        }
    return ;
}

int bc[MAXN], s[19][MAXN], X[19][MAXN], o[MAXN];
void solve_or(){
    rep(i, 0, bc[lim])fwt_or(s[i], 1);
    rep(now, 0, lim)X[0][now] = mul(s[0][now], s[0][now]);
    rep(i, 1, bc[lim]){
        rep(j, 0, i)rep(now, 0, lim)
            inc(X[i][now], mul(s[j][now], s[i - j][now]));
        fwt_or(X[i], -1);
        rep(now, 0, lim)if(bc[now] != i)X[i][now] = 0;
        if(i != bc[lim])fwt_or(X[i], 1);
    }
    rep(i, 0, bc[lim] - 1)fwt_or(X[i], -1);
    rep(now, 0, lim)o[now] = mul(X[bc[now]][now], a[now]);
    return ;
}

int p[MAXN], q[MAXN];
void solve_xor(){
    inv2 = inv(2); fwt_xor(p, 1);
    rep(now, 0, lim)p[now] = mul(p[now], p[now]); fwt_xor(p, -1);
    rep(now, 0, lim)p[now] = mul(p[now], a[now]); return ;
}

void solve_final(){
    rep(now, 0, lim)q[now] = mul(q[now], a[now]);
    fwt_and(o, 1); fwt_and(p, 1); fwt_and(q, 1);
    rep(now, 0, lim)q[now] = mul(o[now], mul(p[now], q[now]));
    fwt_and(q, -1);
    for(int i = 1; i < lim; i <<= 1)inc(ans, q[i]);
    return ;
}

int main(){
    n = read(); int tmp = 0;
    rep(now, 0, 1 << 18)bc[now] = bc[now >> 1] + (now & 1);
    rep(i, 1, n){
        int x = read(); tmp = max(tmp, x);
        s[bc[x]][x]++, p[x]++, q[x]++;
    }
    while(lim - 1 <= tmp)lim <<= 1; lim--;
    a[0] = 0, a[1] = 1; rep(i, 2, lim)a[i] = add(a[i - 1], a[i - 2]);
    solve_or(); solve_xor(); solve_final();
    write(ans); return 0;
}