笨蛋花的小窝qwq

笨蛋花的小窝qwq

“我要再和生活死磕几年。要么我就毁灭,要么我就注定铸就辉煌。如果有一天,你发现我在平庸面前低了头,请向我开炮。”

[NOI Online #3 提高组]优秀子序列

posted on 2020-05-24 19:12:29 | under 题解 |

考虑最后求的是 $\varphi$ 套起来的东西。所以必然要从权值入手。

于是就是考虑有多少个合法子序列的和为 $x$ 。那么就考虑设 $f_{i}$ 表示和为 $i$ 的合法子序列的方案数。考虑如何转移出 $f_i$ 来。不难发现如果一个元素 $j$ 和前面的所有元素的 $\&$ 都为 $0$,这个条件等价于$$ a_{b_j}\&\left(\bigcup_{k=1}^{j-1} a_{b_k}\right)=0\qquad(1) $$ 于是就可以对着这个式子来进行 dp。暴力复杂度可能是 $O(n\cdot \max\{a_i\})$ 的。稍微预处理一下可以通过 $40\%$ 的数据。

并且考虑 $(1)$ 式的本质,发现如果存在 $\geqslant 2$ 个数在某个二进制位上均为 $0$,那么一定是不合法的。 所以一个优秀的子序列,必然满足二进制下每一位,至多有一个数为 1 。那么考虑此时这个序列的和,在二进制下本质上不存在进位。于是可以发现 $f_i$ 同样也是异或和为 $i$ 的合法子序列方案数。

于是考虑对着这个 dp。发现实际上子序列并没有安排序列的选择顺序。于是考虑对于每一种异或和为 $x$ 的方案数,都可以在其中加入某个 $=y$ 的位置使得异或和变为 $x \operatorname{xor} y$ 。于是有转移

$$ f_i=\sum _{j\subseteq i} f_{i}\cdot \operatorname{count}(i\setminus j) $$

其中 $\operatorname{count}(i)$ 表示 $i$ 的出现次数。

但注意这样转移其实是转移了俩方向。于是可以判掉那些和 $i$ 有相同 $\rm lowbit$ 的 $j$ 进行转移。设 $k=\log_2(\max\{a_i\}) $,那么这样做的复杂度是 $O(3^k)$ 。

之后不难发现这就是一个子集卷积的形式。可以考虑枚举 $\rm lowbit$ 来实现转移,复杂度 $O(2^k\cdot k^2)$ 。

int cnt = 1 ;
bool check[M] ;
int prime[M] ;
int phi[M] ;
inline void init(int n){
    phi[1] = 1 ;
    for(int i=2;i<=n;i++){
        if(!check[i]){
            phi[i]=i-1;
            prime[cnt++]=i;
        }
        for(int j=1;j<=cnt;j++){
            if(prime[j]*i>n)break;
            check[i*prime[j]]=1;
            if(i%prime[j]==0)
            {
                phi[i*prime[j]]=prime[j]*phi[i];
                break;
            }
            else
            phi[i*prime[j]]=phi[i]*phi[prime[j]];
        }
    }
}

ll ans ;
int n, m ;
int f[N] ;
int buc[M] ;
int base[N] ;

int expow(int x, int y){
    int res = 1 ; 
    while (y){
        if (y & 1) res = 1ll * res * x % P ; 
        x = 1ll * x * x % P ; y >>= 1 ; 
    }
    return res ;
}

int low(int x){ return x & -x ; }

int main(){
    init(400000) ; int v ; cin >> n ;
    for (int i = 1 ; i <= n ; ++ i)
        buc[base[i] = qr()] ++, chkmax(m, base[i]) ;
    f[0] = expow(2, buc[0]) ;
    v = 1 ; while (v <= m) v <<= 1 ;
    for (int i = 1 ; i <= v ; ++ i)
        for (int j = i ; j >= 0 ; j = (j - 1) & i){
            if (low(i) != low(j))
                add(f[i], 1ll * f[j] * buc[i ^ j] % P) ;
            if (!j) break ;
        }
//    debug(f, 0, 50) ;
    for (int i = 0 ; i <= v ; ++ i)
        if (f[i]) add(ans, 1ll * f[i] * phi[1 + i] % P) ;
    cout << ans << '\n' ; return 0 ;
}