题解：2024牛客暑期多校第1场——A [A Bit Common]

英文题干

Given two integers 𝑛 and 𝑚, among all the sequences containing 𝑛 non-negative integers less than $2^𝑚$ , you need to count the number of such sequences 𝐴 that there exists a non-empty subsequence of 𝐴 in which the bitwise AND of the integers is 1.

Note that a non-empty subsequence of a sequence 𝐴 is a non-empty sequence that can be obtained by deleting zero or more elements from 𝐴 and arranging the remaining elements in their original order.

Since the answer may be very large, output it modulo a positive integer 𝑞.

The bitwise AND of non-negative integers 𝐴 and 𝐵, (𝐴 AND 𝐵) is defined as follows:

When (𝐴 AND 𝐵) is written in base two, the digit in the $2^d$ 's place ( $d\geq 0)$ is 1 if those of 𝐴 and 𝐵 are both 1, and 0 otherwise.

For example, we have (4 AND 6 = 4) (in base two: (100 AND 110 = 100)).

Generally, the bitwise AND of 𝑘 non-negative integers $p_1,p_2,...,p_k$ is defined as (…(( $𝑝_1$ AND $𝑝_2$ ) AND $𝑝_3$ ) AND … AND $𝑝_𝑘$ ) and we can prove that this value does not depend on the order of $p_1,p_2,...,p_k$ .

Input:

The only line contains three integers $n(1\leq n\leq 5000)$ , $m(1\leq m\leq 5000)$ and $q(1\leq q\leq 10^9)$ .

Output:

Output a line containing an integer, denoting the answer.

中文题干

给定两个整数 𝑛 和 𝑚，对于包含 𝑛 个非负整数且小于 $2^𝑚$ 的所有序列，您需要计算其中存在至少一个非空子序列的序列 𝐴 的数量，使得这个子序列中整数的按位 AND 结果为 1。

请注意，序列 𝐴 的非空子序列是指通过从 𝐴 中删除零个或多个元素并按照剩余元素的原始顺序排列而获得的非空序列。

由于答案可能非常大，输出结果需对正整数 𝑞 取模。

非负整数 𝐴 和 𝐵 的按位 AND 运算，(𝐴 AND 𝐵) 的定义如下：

当 (𝐴 AND 𝐵) 用二进制表示时， $2^d$ 位（ $d\geq 0$ ）上的数字为 1，如果 𝐴 和 𝐵 的对应位都为 1，否则为 0。

例如，我们有 (4 AND 6 = 4)（二进制表示为：(100 AND 110 = 100)）。

通常情况下，𝑘 个非负整数 $p_1,p_2,...,p_k$ 的按位 AND 运算被定义为 (…(( $𝑝_1$ AND $𝑝_2$ ) AND $𝑝_3$ ) AND … AND $𝑝_𝑘$ )，并且我们可以证明该值不依赖于 $p_1,p_2,...,p_k$ 的顺序。

思路

Inspired by 命题组

首先我们知道：二进制最低位为0的数是偶数，为1的是奇数。
偶数一定不在 AND和是1的子序列里，这些数除了最低位都可以任选。对于奇数，如果存在一个子序列的 AND和是1，那么包含这个子序列的 AND和也是1。只要序列中所有奇数 AND和是1就能满足条件。
记序列中的奇数有 $k$ 个，这些数除了最低位的 AND和都要是0，即每一位上至少有一个数为0。因此总方案数就是：

$\sum_{k=1}^nC_{n}^k\cdot(2^{(n-k)\cdot (m-1)})\cdot((2^k-1)^{m-1})\\$

$C_{n}^k$ ：n 个数中选 k 个作为奇数
$2^{(n-k)\cdot (m-1)}$ ：剩余的 n-k 个偶数除了最后一位之外，剩下 m-1 位均可选0或1。
$(2^k-1)^{m-1}$ ：选中的 k 个奇数将它们全部表示为 m 位二进制。然后把每一位的 k 个01看成一个二进制数串。这个串不能全是1，否则该位的 k 个1取 AND和之后必然是1，其他情况都是可以的。

AC代码

时间复杂度：O( $n(n m)$ )

#pragma once
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int infmin = 0xc0c0c0c0;
const int infmax = 0x3f3f3f3f;
const int maxn = 5e3 + 10;

int n, m;
ll mod;

// 带余快速幂
ll qpow(ll a, ll b, ll mod)
{
    ll res = 1;
    while (b)
    {
        if (b & 1)
            res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res % mod;
}

// 求组合数
ll C[maxn][maxn];
void getCombination()
{
    C[0][0] = 1;
    for (int i = 1; i <= n; i++)
    {
        C[i][0] = 1;
        C[i][i] = 1;
        for (int j = 1; j < i; j++)
        {
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
        }
    }
}

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

    cin >> n >> m >> mod;

    getCombination();

    ll ans = 0;
    for (ll k = 1; k <= n; k++)
    {
        ll tmp = C[n][k];
        ll x = (qpow(2, n, mod) - qpow(2, n - k, mod) + mod) % mod;
        (tmp *= qpow(x, m - 1, mod)) %= mod;
        (ans += (tmp + mod)) %= mod;
    }

    cout << ans % mod << endl;

    return 0;
}