题解 | #小红的相等数组#

题目链接

REAL740 小红的相等数组

题目描述

小红希望你构造一个长度为 $n$ 的数组，满足：

数组中的每个元素 $a_i$ 满足 $0 \le a_i < 2^k$ 。
数组所有元素的异或和小于等于所有元素的与和。即: $(\bigoplus_{i=1}^n a_i) \le (\&_{i=1}^n a_i)$

小红想知道有多少种可能的方案数。答案对 $10^9+7$ 取模。

思路分析

1. 问题转换：按位分析

问题的核心约束是 异或和 <= 与和。这种涉及位运算的大小比较问题，通常可以从高位到低位逐位确定，这正是动态规划（DP），特别是数位DP (Digit DP) 的典型应用场景。

我们从高到低（从第 $k-1$ 位到第 $0$ 位）来考虑数组中所有 $n$ 个元素的每一位。

令 XOR_sum 的第 $b$ 位为 $X_b$ ，AND_sum 的第 $b$ 位为 $A_b$ 。 XOR_sum <= AND_sum 这个条件成立，当且仅当：

XOR_sum == AND_sum，即对于所有位 $b$ ， $X_b = A_b$ 。
或者，存在一个最高位 $b_{msb}$ ，使得 $X_{b_{msb}} < A_{b_{msb}}$ ，并且对于所有比 $b_{msb}$ 更高的位 $b' > b_{msb}$ ，都有 $X_{b'} = A_{b'}$ 。一旦 $X < A$ 在高位确定下来，低位无论如何取值，最终的大小关系都不会改变。

这个结构天然适合 DP。我们定义状态来记录从高位到当前位的比较结果。

2. DP 状态与转移

我们定义 DP 状态 dp[i][state] 表示考虑了从高到低 $i$ 位（即第 $k-1$ 位到第 $k-i$ 位）之后，满足特定状态的方案数。

dp[i][0]：前 $i$ 位满足 XOR_sum 的高位部分等于 AND_sum 的高位部分的方案数。
dp[i][1]：前 $i$ 位满足 XOR_sum 的高位部分小于 AND_sum 的高位部分的方案数。

DP 过程：我们从 dp[0][0]=1, dp[0][1]=0 (处理0位，高位部分为空，视作相等) 开始，递推计算到 dp[k]。

对于当前位 $b$ ，我们有多少种选择方案（即 $a_{1..n}$ 的当前位如何取值）可以使状态从 equal 变为 equal，从 equal 变为 less，或者从 less 保持 less？

设当前位有 $c$ 个1。

$A_b=1$ 当且仅当 $c=n$ （所有元素的第 $b$ 位都是1）。
$X_b=1$ 当且仅当 $c$ 是奇数。

状态转移系数：

ways_equal：使 $X_b = A_b$ 的方案数。
- $X_b=0, A_b=0$ ： $c$ 是偶数且 $c \ne n$ 。
- $X_b=1, A_b=1$ ： $c$ 是奇数且 $c = n$ （这要求 $n$ 本身是奇数）。
ways_less：使 $X_b < A_b$ 的方案数。
- $X_b=0, A_b=1$ ： $c$ 是偶数且 $c = n$ （这要求 $n$ 本身是偶数）。
ways_any: 任意选择，总共有 $2^n$ 种方案。

利用组合数学恒等式 $\sum_{c \text{ is even}} \binom{n}{c} = \sum_{c \text{ is odd}} \binom{n}{c} = 2^{n-1}$ ，我们可以快速计算出 ways_equal 和 ways_less：

若 $n$ 为偶数：
- ways_equal = (选偶数个1, 但不选n个) = $(\sum_{c \text{ even}}\binom{n}{c}) - \binom{n}{n} = 2^{n-1} - 1$ 。
- ways_less = (选n个1, n是偶数) = $\binom{n}{n} = 1$ 。
若 $n$ 为奇数：
- ways_equal = (选偶数个1) + (选n个1, n是奇数) = $2^{n-1} + 1$ 。
- ways_less = 0 (因为 $n$ 是奇数，不可能满足 $c=n$ 且 $c$ 是偶数)。

DP 递推式 (从 i = 1 到 k):

dp[i][0] = (dp[i-1][0] * ways_equal) % M
dp[i][1] = (dp[i-1][0] * ways_less + dp[i-1][1] * 2^n) % M

最终答案为 (dp[k][0] + dp[k][1]) % M。

代码

cpp
java
python

#include <iostream>
#include <vector>

using namespace std;

long long power(long long base, long long exp) {
    long long res = 1;
    base %= 1000000007;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % 1000000007;
        base = (base * base) % 1000000007;
        exp /= 2;
    }
    return res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k;
    cin >> n >> k;

    long long M = 1000000007;

    long long ways_equal, ways_less;
    long long p2_n_minus_1 = power(2, n - 1);

    if (n % 2 == 0) {
        ways_equal = (p2_n_minus_1 - 1 + M) % M;
        ways_less = 1;
    } else {
        ways_equal = (p2_n_minus_1 + 1) % M;
        ways_less = 0;
    }

    long long p2_n = power(2, n);
    long long dp_equal = 1;
    long long dp_less = 0;

    for (int i = 0; i < k; ++i) {
        long long next_dp_equal = (dp_equal * ways_equal) % M;
        long long next_dp_less = (dp_equal * ways_less + dp_less * p2_n) % M;
        dp_equal = next_dp_equal;
        dp_less = next_dp_less;
    }

    cout << (dp_equal + dp_less) % M << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    static long M = 1_000_000_007;

    public static long power(long base, long exp) {
        long res = 1;
        base %= M;
        while (exp > 0) {
            if (exp % 2 == 1) {
                res = (res * base) % M;
            }
            base = (base * base) % M;
            exp /= 2;
        }
        return res;
    }

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

        long waysEqual, waysLess;
        long p2nMinus1 = power(2, n - 1);

        if (n % 2 == 0) {
            waysEqual = (p2nMinus1 - 1 + M) % M;
            waysLess = 1;
        } else {
            waysEqual = (p2nMinus1 + 1) % M;
            waysLess = 0;
        }

        long p2n = power(2, n);
        long dpEqual = 1;
        long dpLess = 0;

        for (int i = 0; i < k; i++) {
            long nextDpEqual = (dpEqual * waysEqual) % M;
            long nextDpLess = (dpEqual * waysLess + dpLess * p2n) % M;
            dpEqual = nextDpEqual;
            dpLess = nextDpLess;
        }

        System.out.println((dpEqual + dpLess) % M);
    }
}

import sys

def power(base, exp, mod):
    res = 1
    base %= mod
    while exp > 0:
        if exp % 2 == 1:
            res = (res * base) % mod
        base = (base * base) % mod
        exp //= 2
    return res

def solve():
    n, k = map(int, sys.stdin.readline().split())
    M = 10**9 + 7

    p2_n_minus_1 = power(2, n - 1, M)

    if n % 2 == 0:
        ways_equal = (p2_n_minus_1 - 1 + M) % M
        ways_less = 1
    else:
        ways_equal = (p2_n_minus_1 + 1) % M
        ways_less = 0
    
    p2_n = power(2, n, M)
    
    dp_equal = 1
    dp_less = 0
    
    for _ in range(k):
        next_dp_equal = (dp_equal * ways_equal) % M
        next_dp_less = (dp_equal * ways_less + dp_less * p2_n) % M
        dp_equal = next_dp_equal
        dp_less = next_dp_less
        
    print((dp_equal + dp_less) % M)

solve()

算法及复杂度

算法：动态规划（按位DP）
时间复杂度： $O(K \cdot \log N)$ 。DP 循环进行 $K$ 次，每次内部有常数次模乘。预计算转移系数时需要计算模幂，其复杂度为 $O(\log N)$ 。因此总复杂度为 $O(K \log N)$ 。
空间复杂度： $O(1)$ 。DP 状态的转移只需要常数个变量。