思路

题目要求求所有子矩阵中元素之和。已知对于一个 $n \times n$ 的矩阵，元素 $c[i][j]$（下标从 1 开始）出现在所有连续子矩阵中的次数为
因此所有子矩阵的和为

注意 $c[i][j] = a[i] \oplus b[j]$ 对于二进制数可写为

设

• 权值 $w_i = i\times (n-i+1)$（注意题目中下标从1开始，若使用0-index需转换为 $(i+1) \times (n-i)$）
• $S = \sum_{i=1}^{n} w_i$
• $S_a = \sum_{i=1}^{n} a[i] \times w_i$
• $S_b = \sum_{j=1}^{n} b[j] \times w_j$

则有

代码实现

C++

#include <iostream>
#include <vector>
using namespace std;
 
const long long MOD = 1000000007;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++){
        cin >> a[i];
    }
    for (int i = 0; i < n; i++){
        cin >> b[i];
    }
    
    long long S = 0, S_a = 0, S_b = 0;
    // 注意下标转换：题中下标从1开始，因此对于数组下标 i（0-indexed）对应权值为 (i+1)*(n-i)
    for (int i = 0; i < n; i++){
        long long weight = (long long)(i+1) * (n - i) % MOD;
        S = (S + weight) % MOD;
        if(a[i] == 1)
            S_a = (S_a + weight) % MOD;
        if(b[i] == 1)
            S_b = (S_b + weight) % MOD;
    }
    
    long long ans = (S * ((S_a + S_b) % MOD) % MOD - 2LL * S_a % MOD * S_b % MOD) % MOD;
    if(ans < 0) ans += MOD;
    cout << ans << "\n";
    return 0;
}

java

import java.util.Scanner;

public class Main {
    static final long MOD = 1000000007;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        int[] b = new int[n];
        
        for (int i = 0; i < n; i++){
            a[i] = sc.nextInt();
        }
        for (int i = 0; i < n; i++){
            b[i] = sc.nextInt();
        }
        
        long S = 0, S_a = 0, S_b = 0;
        // 下标转换：对应权值为 (i+1)*(n-i)
        for (int i = 0; i < n; i++){
            long weight = (long)(i + 1) * (n - i) % MOD;
            S = (S + weight) % MOD;
            if(a[i] == 1)
                S_a = (S_a + weight) % MOD;
            if(b[i] == 1)
                S_b = (S_b + weight) % MOD;
        }
        
        long ans = (S * ((S_a + S_b) % MOD) % MOD - 2L * S_a % MOD * S_b % MOD) % MOD;
        if(ans < 0) ans += MOD;
        
        System.out.println(ans);
        sc.close();
    }
}

python

import sys

MOD = 1000000007

def main():
    n = int(sys.stdin.readline().strip())
    a = list(map(int, sys.stdin.readline().strip().split()))
    b = list(map(int, sys.stdin.readline().strip().split()))

    S, S_a, S_b = 0, 0, 0

    # 下标转换：对应权值为 (i+1)*(n-i)
    for i in range(n):
        weight = (i + 1) * (n - i) % MOD
        S = (S + weight) % MOD
        if a[i] == 1:
            S_a = (S_a + weight) % MOD
        if b[i] == 1:
            S_b = (S_b + weight) % MOD

    ans = (S * ((S_a + S_b) % MOD) % MOD - 2 * S_a % MOD * S_b % MOD) % MOD
    if ans < 0:
        ans += MOD

    print(ans)

if __name__ == "__main__":
    main()

题目内容

小红有两个长度都为n的数组$a,b$，仅包含$0、1$

现在小红生成一个二维矩阵$c$，满足$c_{i,j}=a_i \bigoplus b_j$

现在小红想让你帮助她计算出其所有子矩阵的数值之和,结果对$10^9+7$取模。

输入描述

第一行一个整数$n(1≤n≤2×10^5)$,表示数组长度。

第二行$n$个整数，第个整数为$a_i(0≤a_i≤1)$。

第二行$n$个整数,第$i$个整数为$b_i(0≤b_i≤1)$。

输出描述

一个整数,表示矩阵$c$的所有子矩阵之和,结果对$10^9+7$取模

样例1

输入

3
1 0 1
0 1 0

输出

52