%qkw 放个注释代码

#include<bits/stdc++.h>
using namespace std;

#define int long long 
const int N = 2e5 + 10;
const int P = 1e9 + 7;

vector<int> G[N];
int n, m, k, Gcd, Lcm;
int A[N], B[N];
int a[N], b[N];
int ans;
int fit[N];

int gcd(int x, int y) {   // 不知道为啥啊 vscode 用不了系统自带 __gcd 
    while (y) {
        int temp = y;
        y = x % y;
        x = temp;
    }
    return x;
}

int solve() {
    int rlen = m / Gcd;   // 每个环的长度 
    int res = 0;

    for (int i = 0; i < Gcd; i ++) {
        G[i].clear();
        G[i].push_back(0);
        for (int j = 0, k = i; j < rlen; j ++, k = (k + n) % m) {
            fit[k] = j + 1;     // 环上点对应下标 
            G[i].push_back(b[k]);
        }
        for (int j = 0; j < rlen; j ++) {    // 复制一遍环到后面 
            G[i].push_back(G[i][j + 1]);
        }
        for (int j = 1; j < G[i].size(); j ++) {   // 计算前缀和 
            G[i][j] += G[i][j - 1];
        }
    }

    for (int i = 0; i < n; i ++) {
        int pos = fit[i % m];    // 取当前 Ai 对应的 B 对应的在环上下标 
        int cnt = (k - i) / Lcm % P;   // k 挖掉 i 之前的，取整段环 
        int ac = ((k - i) % Lcm + n - 1) / n;  // 剩下的环 
        // 为啥除以 n 上取整？因为 Ai 每 n 个位置出现一次
		// 而 k - i 挖掉 i 之前的，一旦有余数那肯定第一个就是 Ai 

        if (i == k) break;  // 如果已经处理到 k 位置，退出循环
        if (cnt < 0) cnt = 0;
        
        if (a[i] == 0) {
            res = (res + cnt * G[i % Gcd][rlen] % P + 
                   G[i % Gcd][pos + ac - 1] - G[i % Gcd][pos - 1]) % P;
        } 
        else {   // 等于 1 就计算 0 的个数 
            res = (res + cnt * (rlen - G[i % Gcd][rlen]) % P + 
                   ac - G[i % Gcd][pos + ac - 1] + G[i % Gcd][pos - 1]) % P;
        }
        res = (res + P) % P;
    }

    return res;
}

signed main () {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m >> k;
    Gcd = gcd(n, m);
    Lcm = n / Gcd * m;
    
    for (int i = 0; i < n; i ++) cin >> A[i];
    for (int i = 0; i < m; i ++) cin >> B[i];

    // 确保 n >= m
    if (n < m) {
        for (int i = 0; i < m; i ++) swap(A[i], B[i]);
        swap(n, m);
    }

    ans = 0;
    for (int bit = 0; bit <= 60; bit ++) {   // 枚举二进制位 
        for (int i = 0; i < n; i ++) {
            a[i] = (A[i] >> bit) & 1;
        }
        for (int i = 0; i < m; i ++) {
            b[i] = (B[i] >> bit) & 1;
        }
        int pow2 = (1LL << bit) % P;    // 该二进制位权值 
        ans = (ans + solve() * pow2 % P) % P;   // 累计答案 
    }

    cout << ans << "\n";

    return 0;
}

依旧好想难写题。拥有超级多的细节（场上调了 1h 才切掉）。

首先我们可以对每一个数位分别求一次答案。

然后易发现每 $lcm(n,m)$ 次会形成一个循环，$a$ 中的每个数都会和 $b$ 中的每个数匹配一次。现在考虑 $k<lcm(n,m)$ 的情况。

又发现当 $\gcd(n,m) \neq 1$ 时，每一个数其实不会和所有其它数匹配，只会和与 $\gcd(n,m)$ 同余的下标进行匹配。所以我们可以将整个序列分成 $\gcd(n,m)$ 个小块分别计算。

目前的问题是如何求出对于每一个 $i \in [1,n]$，$a_i$ 会在这 $k$ 个数中与哪些数匹配。

好了，现在 $k < lcm(n,m)$ 且 $\gcd(n,m)=1$ 了。我们开始打表吧。

假定 $n=7,m=4$，我们定义 $S_i$ 为 $a_i$ 会依次匹配的 $b$ 的元素下标。

则：

发现了什么？居然是一个环？

那还说啥了，直接重组 $b$ 数组然后断环为链前缀和啊。

剩下的注意细节就行。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=4e5+10,P=1e9+7;
int a[N],b[N],c[N],d[N],s[N],p[N];
signed main()
{
	int n,m,k;cin>>n>>m>>k;
	int len=__gcd(n,m),pub=k/(n*m/len),k1=k%(n*m/len),ans=0;pub%=P;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=m;i++)cin>>b[i];
	for(int i=1,l=0;i<=len;i++)
	{
		int pos=i-1;
		for(int j=1;j<=m/len;j++)
			c[++l]=pos+1,p[pos+1]=l,pos=(pos+n)%m;
		for(int j=1;j<=m/len;j++)
			c[++l]=pos+1,pos=(pos+n)%m;
	}
	for(int i=60;i>=0;i--)
	{
		int sum=0;
		for(int j=1;j<=m*2;j++)d[j]=(bool)(b[c[j]]&(1ll<<i));
		for(int j=1;j<=m*2;j++)s[j]=s[j-1]+d[j];
		for(int j=1;j<=n;j++)
		{
			int id=(j-1)%len,res=k1/n+(k1%n>=j),st=p[(j-1)%m+1]-1;
			if(a[j]&(1ll<<i))
			{
				sum=(sum+res-(s[st+res]-s[st]))%P;
				sum=(sum+(m/len-(s[st+m/len]-s[st]))*pub)%P;
			}
			else
			{
				sum=(sum+s[st+res]-s[st])%P;
				sum=(sum+(s[st+m/len]-s[st])*pub)%P;
			}
		}
		ans=(ans+sum*((1ll<<i)%P)%P)%P;
	}
	cout<<ans;
	return 0;
}

P11431

题目意思其实就是给定 $n,m$ 和两个无限循环的数组 $a_1$ 到 $a_n$ ，$b_1$ 到 $b_m$ 在给定一个 $k$ 求 $$\sum_{i=1}^k a_i \oplus b_i$$ 我们注意到 $\oplus$ 也就是异或运算，有异或，那就好办了，我们可以把，每个 $a_i$ 和 $b_i$ 转换为二进制，依次比较，遍历到有一时，就加贡献值。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
int n,m,k,a[200005],b[200005],r[200005],gcd,lcm;
vector<int> v[200005];
int solve(vector<int> A,vector<int> B){
	int mm=m/gcd;
	for(int i=0;i<gcd;i++){
		v[i].clear(),v[i].push_back(0);
		for(int j=1,s=i;j<=mm;j++,s=(s+n)%m){
			r[s]=j;
			v[i].push_back(B[s]);
		} 
		for(int j=0;j<mm;j++) v[i].push_back(v[i][j+1]);
		for(int j=1;j<v[i].size();j++) v[i][j]+=v[i][j-1];
	}
	int ans=0;
	for(int i=0;i<n;i++){
		int f=(k-i)/lcm%mod;
		int ys=((k-i)%lcm+n-1)/n;
		int f1=r[i%m];
		if(i==k) break;
		if(A[i]==0) ans=((ans+v[i%gcd][mm]*f%mod)%mod+v[i%gcd][f1+ys-1]-v[i%gcd][f1-1])%mod;
        else ans=((ans+(mm-v[i%gcd][mm])*f)%mod+ys-v[i%gcd][f1+ys-1]+v[i%gcd][f1-1])%mod;
	}
	return ans;
}
signed main(){
	cin>>n>>m>>k;
	gcd=__gcd(n,m);lcm=n*m/gcd;
	for(int i=0;i<n;i++) cin>>a[i];
	for(int i=0;i<m;i++) cin>>b[i];
	int num=0;
	for(int i=0,j=1;i<62;i++,j=(j*2)%mod){
		vector<int> A,B;
		for(int x=0;x<n;x++) A.push_back(a[x]>>i&1);
		for(int x=0;x<m;x++) B.push_back(b[x]>>i&1);
		num=(num+solve(A,B)*j%mod)%mod;
	}
	cout<<num;
	return 0;
}