Not Quite Lee(思维裴蜀定理容斥)

Not Quite Lee(思维/裴蜀定理/容斥)

题目
参考
题意：给定长度为 n n n的数组 a i a_i ai​，求出数组 a i a_i ai​的所有为good的子序列的个数。
一个长度为 k k k的数组 b i b_i bi​称为good，当且仅当存在k组序列 c i c_i ci​，每组序列的长度分别为 b i b_i bi​，每个序列的元素都是连续递增或连续递减的，且这些序列的总和 s u m c i = 0 sum_{c_i}=0 sumci​​=0。
思路：分析一个数组 b b b是否可以成为good。

1、 如果数组 b b b存在若干个（1个或多个）奇数，则它可以成为good。因为奇数长度的数组本身总和可以取0（取数时以0为对称轴即可）。同时奇数数组也可以和偶数数组拼接成一个新的、总和为0的奇数数组。

2、如果数组 b b b元素都为偶数。
有结论：有相同lowbit的两个数，可以凑成和为0的两个序列（lowbit就是一个数的二进制的第一个为1的低位）。如2和6（{-2 -1 0 1 2 3} + {-2 -1}），2和10（{-4 -3 -2 -1 0 1 2 3 4 5} + {-3 -2}）。
证明：对于相同lowbit的数x和y。设x的序列的和为 s u m x = ( 1 + x ) ∗ x / 2 + k ∗ x = x / 2 + ( k + x / 2 ) ∗ x sum_x=(1+x)*x/2+k*x=x/2+(k+x/2)*x sumx​=(1+x)∗x/2+k∗x=x/2+(k+x/2)∗x，令 m = k + x / 2 m=k+x/2 m=k+x/2，有 s u m x = x / 2 + m 1 ∗ x sum_x=x/2+m_1*x sumx​=x/2+m1​∗x；同理 s u m y = y / 2 + m 2 ∗ y sum_y=y/2+m_2*y sumy​=y/2+m2​∗y。所以 s u m = s u m x + s u m y = m 1 ∗ x + m 2 ∗ y + ( x + y ) / 2 sum=sum_x+sum_y=m_1*x+m_2*y+(x+y)/2 sum=sumx​+sumy​=m1​∗x+m2​∗y+(x+y)/2，要使 s u m = 0 sum=0 sum=0，有 m 1 ∗ x + m 2 ∗ y = − ( x + y ) / 2 m_1*x+m_2*y=-(x+y)/2 m1​∗x+m2​∗y=−(x+y)/2，根据裴蜀定理，有 g d b ( x , y ) ∣ ( x + y ) / 2 gdb(x,y)|(x+y)/2 gdb(x,y)∣(x+y)/2，即 2 ∗ g d b ( x , y ) ∣ ( x + y ) 2*gdb(x,y)|(x+y) 2∗gdb(x,y)∣(x+y)，即 2 ∣ ( x + y ) g d b ( x , y ) 2|frac{(x+y)}{gdb(x,y)} 2∣gdb(x,y)(x+y)​。因为数x和y有相同lowbit，所以 l o w b i t ( x + y ) > = l o w b i t ( g d b ( x , y ) ) + 1 lowbit(x+y)>=lowbit(gdb(x,y))+1 lowbit(x+y)>=lowbit(gdb(x,y))+1，所以 2 ∣ ( x + y ) g d b ( x , y ) 2|frac{(x+y)}{gdb(x,y)} 2∣gdb(x,y)(x+y)​成立。
根据该结论，我们可以理解为，有相同lowbit的数，可以充当一个奇数的作用。那么我们可以用容斥，枚举计算答案。
官方代码

//In The Name of God
//I usually forget about the previous line...

#include 

#define IOS ios::sync_with_stdio(0), cin.tie(), cout.tie();

using namespace std;

typedef long long ll;

const int maxBt = 30;
const int mod = 1e9+7;

int cnt[maxBt];

int slv(){
    int n;
    cin >> n;

    int a[n];
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }

    int to[n+1]; //powers of 2

    to[0] = 1;
    for(int i = 1; i <= n; i++){
        to[i] = to[i-1]*2 % mod;
    }

    for(int i = 0; i < n; i++){
        int x = 0;
        for(int k = 0; k < maxBt; k++){
            if(a[i] & 1)break;
            a[i] >>= 1;
            x++;
        }
        cnt[x]++;
    }
    // 至少有一个奇数的情况
    int ans = to[n] - to[n-cnt[0]] + mod;
    if(ans >= mod)ans -= mod;

    int y = n-cnt[0];


	// 从小到大枚举lowbit为1到29的情况 
    for(int l = 1; l < maxBt; l++){
        int x = y;
        y -= cnt[l];
        if(x-y < 2)continue;
        // 这里to[x-1]，表示取从cnt[l]取偶数个, 同时从 x - cnt[l]取任意个 
        // to[y]表示从cnt[l]取0个，从 x - cnt[l]取任意个
        // 从cnt[l]取偶数个，刚好是  从cnt[l]取任意个 的 一半 
        int delta = to[x-1]-to[y]+mod;
        if(delta >= mod)delta -= mod;
        ans += delta;
        if(ans >= mod)ans -= mod;
    }

    return ans;
}


signed main(){
    IOS

    cout << slv() << 'n';

}