[NOI Online #3 提高组]优秀子序列
皎月半洒花
2020-05-24 19:12:29
考虑最后求的是 $\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 ;
}
```