CF Goodbye 2020
littlechai
2020-12-31 11:34:46
[E. Apollo versus Pan](http://codeforces.com/contest/1466/problem/E)
题意: 求$\sum\limits_{i=1}^n\sum\limits_{j=1}^n\sum\limits_{k=1}^n$($x_i$&$x_j$)($x_j$|$x_k$)
思路：按位处理，首先预处理每一位的1有多少个，枚举每一个数$x_j$枚举其位数l，则$\sum\limits_{i=1}^n\sum\limits_{j=1}^n\sum\limits_{k=1}^n$($x_i$&$x_j$)($x_j$|$x_k$)$ 若该位为1，结果为n*2^l$否则为cnt[j] * $2^l$考虑该数每一位对答案的贡献，只有该为为1时才对答案有影响$\sum\limits_{i=1}^n$($x_i$&$x_j$) = cnt[j]*$2^l$.
```cpp
#include<bits/stdc++.h>
#define ri register int
#define ll long long
#define lson rt << 1, l, mid
#define rson rt << 1|1, mid+1, r
using namespace std;
void re(ll &x){
x = 0;
int b = 0;
char ch = getchar();
while(ch < '0' || ch > '9'){
if(ch == '-') b = 1;
ch = getchar();
}
while(ch >= '0' && ch <= '9'){
x = (x << 1) + (x << 3) + ch - '0';
ch = getchar();
}
if(b == 1)
x *= -1;
}
const int maxn = 510000;
const int p = 1e9+7;
ll n, m, t;
ll a[maxn], v[100], vis[70];
ll pw[maxn], q[maxn];
int main(){
re(t);
q[0] = 1;
for(int i = 1;i <= 60;i ++){
q[i] = q[i-1]*2;
}
while(t --){
re(n);
memset(v,0,sizeof(v));
ll ans = 0;
for(int i = 1;i <= n;i ++){
re(a[i]);
ll x = a[i];
for(int j = 0;j <= 60;j ++){
if(q[j] & x){
v[j] ++;
}
}
}
for(int i = 1;i <= n;i ++){
ll x = a[i];
ll res = 0;
for(int j = 0;j <= 60;j ++)
vis[j] = 0;
for(int j = 0;j <= 60;j ++){
if(q[j] & x){
vis[j] ++;
res = (res + n*(q[j]%p)%p)%p;
}
else res = (res + v[j]*(q[j]%p)%p)%p;
}
for(int j = 0;j <= 60;j ++){
if(vis[j]) ans = (ans + v[j]*res%p*(q[j]%p)%p)%p;
}
}
printf("%lld\n",ans);
}
return 0;
}
```
[F. Euclid's nightmare](http://codeforces.com/contest/1466/problem/F)
题意：给定一个n个m维向量，m维向量至多两维坐标是1，其余都是0。定义矢量加法u+v = w, wi = (ui+vi)%2，让你求1，n个向量任意组合形成的集合大小（包括空集）
，2，最小能组成全集的向量子集大小，并输出其中的向量编号。
思路：把维度当成点，向量当作边，假设每个向量都有两维有值（一维的另一维为m+1），那么mst即为答案（非mst上的向量可由mst上向量线性组合得到）
```cpp
#include<bits/stdc++.h>
#define ri register int
#define ll long long
#define lson rt << 1, l, mid
#define rson rt << 1|1, mid+1, r
using namespace std;
void re(int &x){
x = 0;
int b = 0;
char ch = getchar();
while(ch < '0' || ch > '9'){
if(ch == '-') b = 1;
ch = getchar();
}
while(ch >= '0' && ch <= '9'){
x = (x << 1) + (x << 3) + ch - '0';
ch = getchar();
}
if(b == 1)
x *= -1;
}
const int maxn = 510000;
const int p = 1e9+7;
int n, m, t;
int fa[maxn], ans[maxn], cnt;
int find(int x){
if(x != fa[x]) fa[x] = find(fa[x]);
return fa[x];
}
void merge(int x, int y){
int fx = find(x);
int fy = find(y);
if(fx != fy) fa[fx] = fy;
}
int main(){
re(n), re(m);
for(int i = 1;i <= m+1;i ++)
fa[i] = i;
ll res = 1;
for(int i = 1;i <= n;i ++){
int k, x, y = m+1;
re(k);
re(x);
if(k > 1) re(y);
if(find(x) != find(y)){
merge(x, y);
ans[++ cnt] = i;
}
}
for(int i = 1;i <= cnt;i ++)
res = res*2%p;
printf("%lld %d\n",res,cnt);
sort(ans+1,ans+1+cnt);
for(int i = 1;i < cnt;i ++)
printf("%d ",ans[i]);
printf("%d",ans[cnt]);
return 0;
}
```