小红的相等数组

[题目链接](https://www.nowcoder.com/practice/d45de1dae26a49bca9d8832b9551737f)

思路

构造长度为 $n$ 的数组，每个元素在 $[0, 2^k - 1]$ ，要求所有元素的异或和 $X$ 不超过与和 $A$ 。统计方案数，对 $10^9 + 7$ 取模。

逐位分析

异或和与按位与都是逐位运算。对于第 $b$ 位，设 $c_b$ 为 $n$ 个元素中该位为 1 的个数，则：

AND 第 $b$ 位 $= 1$ 当且仅当 $c_b = n$
XOR 第 $b$ 位 $= 1$ 当且仅当 $c_b$ 为奇数

要满足 $X \le A$ ，从最高位到最低位扫描，第一个 $A$ 和 $X$ 不同的位必须是 $A = 1, X = 0$ （即 $A$ 在该位赢了）。

每一位有三种状态：

状态	条件	含义
相等 (E)	$c_b = n$ 且 $n$ 为奇数，或 $c_b < n$ 且 $c_b$ 为偶数	$A_b = X_b$
A 赢 (A)	$c_b = n$ 且 $n$ 为偶数	$A_b = 1, X_b = 0$
X 赢 (X)	$c_b < n$ 且 $c_b$ 为奇数	$A_b = 0, X_b = 1$

每一位的 $c_b$ 取值对应 $\binom{n}{c_b}$ 种数组分配方式。定义：

$ $f_E = \sum_{\text{type E}} \binom{n}{c_b}, \quad f_A = \sum_{\text{type A}} \binom{n}{c_b}, \quad f_X = \sum_{\text{type X}} \binom{n}{c_b}$ $

利用 $\sum_{j \text{ even}} \binom{n}{j} = \sum_{j \text{ odd}} \binom{n}{j} = 2^{n-1}$ ，可得：

$n$ 为奇数时： $f_A = 0$ ， $f_E = 2^{n-1} + 1$ ， $f_X = 2^{n-1} - 1$

由于没有位能让 $A$ 赢，唯一满足条件的情况是所有位都相等（ $X = A$ ），答案为 $f_E^k = (2^{n-1} + 1)^k$ 。

$n$ 为偶数时： $f_A = 1$ ， $f_E = 2^{n-1} - 1$ ， $f_X = 2^{n-1}$

计算答案

$k$ 个位各自独立选择状态。合法方案要求从高位到低位，第一个非 E 位必须是 A。枚举第一个非 E 位的位置 $i$ （ $0$ 到 $k-1$ ），前 $i$ 位全为 E，第 $i$ 位为 A，后面 $k-1-i$ 位任意（共 $2^n$ 种选择）：

$ $\text{ans} = f_E^k + \sum_{i=0}^{k-1} f_E^i \cdot f_A \cdot (2^n)^{k-1-i}$ $

其中 $f_E^k$ 对应全部位都相等的情况。由于 $f_A = 1$ ，利用等比数列求和：

$ $\text{ans} = f_E^k + \frac{(2^n)^k - f_E^k}{2^n - f_E} = f_E^k + \frac{2^{nk} - f_E^k}{2^{n-1} + 1}$ $

分母 $2^{n-1} + 1$ 用费马小定理求逆元即可。

复杂度分析

时间复杂度： $O(\log n + \log k)$ ，仅需若干次快速幂。
空间复杂度： $O(1)$ 。

代码

C++
Java

#include <iostream>
using namespace std;

const long long MOD = 1e9 + 7;

long long power(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

int main() {
    long long n, k;
    cin >> n >> k;

    long long T = power(2, n, MOD);

    if (n % 2 == 1) {
        long long half = power(2, n - 1, MOD);
        long long fE = (1 + half) % MOD;
        cout << power(fE, k, MOD) << endl;
    } else {
        long long half = power(2, n - 1, MOD);
        long long fE = (half - 1 + MOD) % MOD;
        long long Tk = power(T, k, MOD);
        long long fEk = power(fE, k, MOD);
        long long denom = (half + 1) % MOD;
        long long num = (Tk - fEk + MOD) % MOD;
        long long inv_denom = power(denom, MOD - 2, MOD);
        long long ans = (fEk + num % MOD * inv_denom % MOD) % MOD;
        cout << ans << endl;
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    static final long MOD = 1_000_000_007;

    static long power(long base, long exp, long mod) {
        long result = 1;
        base %= mod;
        while (exp > 0) {
            if ((exp & 1) == 1) result = result * base % mod;
            base = base * base % mod;
            exp >>= 1;
        }
        return result;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        long k = sc.nextLong();

        long T = power(2, n, MOD);

        if (n % 2 == 1) {
            long half = power(2, n - 1, MOD);
            long fE = (1 + half) % MOD;
            System.out.println(power(fE, k, MOD));
        } else {
            long half = power(2, n - 1, MOD);
            long fE = (half - 1 + MOD) % MOD;
            long Tk = power(T, k, MOD);
            long fEk = power(fE, k, MOD);
            long denom = (half + 1) % MOD;
            long num = (Tk - fEk + MOD) % MOD;
            long invDenom = power(denom, MOD - 2, MOD);
            long ans = (fEk + num % MOD * invDenom % MOD) % MOD;
            System.out.println(ans);
        }
    }
}