Practice.

A. Joey Takes Money

题意

给定一个包含 \(n\) 个 \(\geq 1\) 的元素的数组 \(a\)，定义操作为：

选定 \(i, j, i \neq j\)；
选两个 \(\geq 1\) 的正整数 \(x, y\)，满足 \(x \cdot y = a_i \cdot a_j\)；
将 \(a_i, a_j\) 改为 \(x, y\)。

输出任意次操作后数组的和的最大值 x2022。

思路

显然，对于 \(a_i, a_j\)，\(1 + a_i \cdot a_j\) 一定是所有操作中最大的和，那么我们可以依次从左到右将所有数都执行一遍该操作，得到 \(1, 1, 1, \ldots, \prod a_i\)，求和即可。

时间复杂度：\(O(n)\)

对应AC代码

import java.util.*;

public class Main{

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        while(t-- > 0){
            int n = scanner.nextInt();
            long[] a = new long[n];
            for(int i=0;i<n;i++) a[i] = scanner.nextInt();
            Arrays.sort(a);
            for(int i=0;i<n-1;i++){
                a[n - 1] = a[n - 1] * a[i];
                a[i] = 1;
            }
            System.out.println(2022 * ((long) (n - 1) + a[n - 1]));
        }
    }
}

简单思维题 & 2022x1

B. Kill Demodogs

题意

给定一个 \(n \times n\) 的矩阵，\((i, j)\) 位置的元素值为 \(i \times j\)。定义人物从 \((1, 1)\) 走到 \((n, n)\)，期间人物只能向下或向右移动一格，输出到达终点后经过的元素的值的总和的最大值。

思路

显然，我们走对角线是最优的，此时横坐标和纵坐标的值最相近。

此时，我们可以得到下面的式子：

\(1 \times 1 + 1 \times 2 + 2 \times 2 + \ldots + (n - 1) \times n + n \times n\)。

我们将其拆成两个式子：

\(1 \times 1 + 2 \times 2 + \ldots + n \times n\)；
\(1 \times 2 + 2 \times 3 + \ldots + (n - 1) \times n\)。

对于上述两个式子，我们套用公式即可。

最后，我们可以得到下面的式子：

\(\frac{n (n + 1) (2n + 1)}{6} + \frac{(n - 1) n (n + 1)}{3}\)。

此时，我们有两个选择：大数或者逆元。任选其一即可。

时间复杂度：\(O(1)?\)

对应AC代码

import java.math.BigInteger;
import java.util.*;

public class Main{

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt(), mod = 1000000007;
        while(t -- > 0){
            long n = scanner.nextInt();
            System.out.println((2022 *
                    ((BigInteger.valueOf(n).multiply(BigInteger.valueOf(n + 1)).multiply(BigInteger.valueOf(2 * n + 1)).divide(BigInteger.valueOf(6)).mod(BigInteger.valueOf(mod)).longValue() +
                            BigInteger.valueOf(n - 1).multiply(BigInteger.valueOf(n)).multiply(BigInteger.valueOf(n + 1)).divide(BigInteger.valueOf(3)).mod(BigInteger.valueOf(mod)).longValue()) % mod)) % mod);
        }
    }
}

大数yyds

C. Even Subarrays

题意

给定一个长度为 \(n\) 的数组 \(a\)，\(1 \leq a_i \leq n\)，输出连续的子序列的个数，子序列需满足子序列的异或值有偶数个因数。

思路

这里需要用到一个性质：只有完全平方数的因数数量是奇数。

所以，我们不妨找完全平方数，然后取一个补集即可。

考虑到异或的交换性，我们不妨用答案来枚举。

更具体地说，我们不妨从前向后遍历，\(cur\) 为前 \(i\) 个元素的异或值，我们用 \(m\) 数组存储这些异或值出现的次数，然后，我们枚举所有可能的答案，算出 \(cur\) 需要和前面的哪一段区间的异或值进行异或后得到完全平方数，用类似于前缀和的方式记录答案。

考虑到 \(a_i\) 的范围，我们只需枚举 \(2n\) 及以下的完全平方数即可。

时间复杂度：\(O(n \sqrt n)\)

对应AC代码

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        while(t -- > 0){
            int n = scanner.nextInt();
            int[] a = new int[n];
            for(int i=0;i<n;i++) a[i] = scanner.nextInt();
            long[] m = new long[2 * n];
            int cur = 0;
            long cnt = 0;
            m[cur] = 1;
            for(int i=0;i<n;i++){
                cur ^= a[i];
                for(int j=0;j*j<2*n;j++){
                    int now = cur ^ (j * j);
                    if(now < 2 * n) cnt += m[now];
                }
                m[cur] ++;
            }
            System.out.println((long) n * (n - 1) / 2 + n - cnt);
        }
    }

}

异或的性质太多力