Codeforces Round #626 (Div. 2, based on Moscow Open Olympiad in Informatics)

给定大小为$n$的a数组，求下面式子的结果：

$$ (a_1 + a_2) \oplus (a_1 + a_3) \oplus \ldots \oplus (a_1 + a_n) \\ \oplus (a_2 + a_3) \oplus \ldots \oplus (a_2 + a_n) \\ \ldots \\ \oplus (a_{n-1} + a_n) \\$$

这题看了题解补的

分别求结果的第$k$(以0开始计数)位是否为1

显然，我们不需要关心每个数第$k$位以上是什么，那么对数组取模$2^{k+1}$

两个数的和的第$k$位为1时，才对答案的第$k$位有贡献，那么和的第$k$位为1需要属于$[2^k; 2^{k+1})$或者$[2^{k+1} + 2^k; 2^{k+2} - 2]$，求出这样的和的对数，如果对数为奇数，那么答案的第$k$位为1，否则为0

求对数可以用二分查找来求

#include
using namespace std;
#define rep(i,a,b) for (int i=a;i<=b;i++) #define per(i,a,b) for (int i=b;i>=a;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define SZ(x) ((int)(x).size())

typedef long long ll;
typedef vector VI;
typedef pair PII;

const ll mod=1e5+7;
const int maxn=4e5+7;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}

int ans,a[maxn],b[maxn],n;
int pow2[30];

int cal(int k){
ll res=0;
rep(i,1,n)b[i]=a[i]%(1<<(k+1)); sort(b+1,b+1+n); rep(i,1,n){ int x=b[i]; // cout<<"x="<=pow2[k]&&x*2<=pow2[k+1]-1)res--; else if(x*2>=pow2[k]+pow2[k+1])res--;
res+=upper_bound(b+1,b+1+n,pow2[k+1]-1-x)-lower_bound(b+1,b+1+n,pow2[k]-x);
res+=upper_bound(b+1,b+1+n,1e9)-lower_bound(b+1,b+1+n,pow2[k]+pow2[k+1]-x);
}
// cout<<"res="<<res<<endl;
return res/2%2;
}

int main() {
// cout<<(1<<24)<<endl;
rep(i,0,29)pow2[i]=(1<<i);
scanf("%d",&n);
rep(i,1,n)scanf("%d",&a[i]);
rep(i,0,25)if(cal(i))ans+=(1<<i);
printf("%d\n",ans);

return 0;  

}

在一个$2n$个节点，$m$条边的二分图中，右边部分每个节点有一个权值

构建一个左边节点的子集$S$，所有和这些子集有边的右边节点构成点集$N(S)$，$N(S)$的所有节点权值和为$F(S)$

求所有$F(S)$的最大公约数

首先是结论，给右边点分类，如果两个点的边集相同，那么他们属于一类

边集相同的意思是，他们所连接的左边节点的数量和类型一模一样

属于相同类的节点权值相加，然后再取所有类的最大公约数，就是最后的答案了

证明：如果两个点属于一类，那么只要有其中一个点出现，另一个点肯定出现，这是显然的

所以，如果这些类的权值依次为$a，b，c$的话，$F(S)$只能取$a,b,c,a+b,a+c,b+c,a+b+c$，这些数的$gcd$是等于$gcd(a,b,c)$的

哈希的话，居然可以用vector直接哈希，这个我完全没想到

注意：vector需要排好序

#include
using namespace std;
#define rep(i,a,b) for (int i=a;i<=b;i++) #define per(i,a,b) for (int i=b;i>=a;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define SZ(x) ((int)(x).size())

typedef long long ll;
typedef vector VI;
typedef pair PII;

const ll mod=1e5+7;
const int maxn=5e5+7;

ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}

int g=1331,n,m;
mapma;
ll powg[maxn];
VI ve[maxn];
ll c[maxn];

int main() {
powg[0]=1;
rep(i,1,maxn-1)powg[i]=powg[i-1]*g;
int T;
scanf("%d",&T);
while(T--){

    scanf("%d %d",&n,&m);  
    rep(i,1,n)scanf("%lld",&c\[i\]);  
    rep(i,1,m){  
        int a,b;  
        scanf("%d %d",&a,&b);  
        ve\[b\].pb(a);  
    }  
    rep(i,1,n){  
        ll res=0;  
        for(auto j:ve\[i\])  
            res+=powg\[j\];  
        if(SZ(ve\[i\]))ma\[res\]+=c\[i\];  
    }  
    ll ans=0;  
    for(auto i:ma)  
        ans=\_\_gcd(i.se,ans);  
    printf("%lld\\n",ans);  
    ma.clear();  
    rep(i,1,n)ve\[i\].clear();  
}  
return 0;  

}

#include
using namespace std;
#define rep(i,a,b) for (int i=a;i<=b;i++) #define per(i,a,b) for (int i=b;i>=a;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define SZ(x) ((int)(x).size())

typedef long long ll;
typedef vector VI;
typedef pair PII;

const ll mod=1e5+7;
const int maxn=5e5+7;

ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}

ll c[maxn];
int n,m;
mapma;
VI ve[maxn];

int main() {
int T;
scanf("%d",&T);
while(T--){

    scanf("%d %d",&n,&m);  
    rep(i,1,n)scanf("%lld",&c\[i\]);  
    rep(i,1,m){  
        int a,b;  
        scanf("%d %d",&a,&b);  
        ve\[b\].pb(a);  
    }  
    rep(i,1,n){

        if(SZ(ve\[i\])){  
            sort(ve\[i\].begin(),ve\[i\].end());  
            ma\[ve\[i\]\]+=c\[i\];  
        }  
    }  
    ll ans=0;  
    for(auto i:ma){  
        ans=gcd(i.se,ans);  

// cout<<i.se<<endl;
}
printf("%lld\n",ans);
ma.clear();
rep(i,1,n)ve[i].clear();
}
return 0;
}