E. Apollo versus Pan

题意: 求$\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$.

#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 题意:给定一个n个m维向量,m维向量至多两维坐标是1,其余都是0。定义矢量加法u+v = w, wi = (ui+vi)%2,让你求1,n个向量任意组合形成的集合大小(包括空集) ,2,最小能组成全集的向量子集大小,并输出其中的向量编号。 思路:把维度当成点,向量当作边,假设每个向量都有两维有值(一维的另一维为m+1),那么mst即为答案(非mst上的向量可由mst上向量线性组合得到)

#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;
}