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

皎月半洒花

2020-05-24 19:12:29

Solution

考虑最后求的是 $\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)$ 。 ```cpp 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 ; } ```