一、题目描述

原题链接

求有多少长为n的元素是 $[0,2m)$ 的整数序列 满足存在一个非空子序列的AND和是 $1$，答案对输入的正整数 $q$ 取模。

二、解题思路

  题目中说找到一个序列，只需要其中的一个子序列满足条件即可，我们设其中选中作为与运算和计算的元素有 $k$ 个，则有 $n - k$ 个元素不参与运算，为了保证不重不漏，其中选中的 $n$ 个数中的 $k$ 个则为 $C^{k}_{n}$，剩下没有选中参与运算的则为 $C^{n-k}_{n-k}$。

  我们先考虑不参与运算的情况，在不参与运算的数字则可以理解为一定无法作为使用条件的，其中显然当二进制位中最后一位为 $0$ 时，一定无法条件，此时一定无法进行运算，统计这样的方案数，即：前 $m-1$ 位随便选，最后一位一定为 $0$，这样的数一共有 $n-k$ 个，所以总方案数为 $2^{(m-1)·(n-k)}$。

  接下来考虑参与运算的情况，考虑何时条件不成立？很显然当 $k$ 个数中的存在一位 $p$（不包含最后一位），使得这 $k$ 个数中的第 $p$ 位全部为 $1$ 时，此时无法满足题目条件，换言之，对于这 $k$ 个数中 的第 $p$ 位，取值范围为

因此一共有 $m - 1$ 位，故此时的方案数为 $(2^k-1)^{m-1}$。

  综上所述，枚举 $k$，求解答案，表达式为：$C^{k}_{n}·C^{n-k}_{n-k}·2^{(m-1)·(n-k)}·(2^k-1)^{m-1}$。

三、AC代码

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll n,m,q;

const int N = 5010;
// const int mod = 1e9 + 7;
int c[N][N];

void init(){
    for(int i = 0;i<N;i++){
        for(int j = 0;j<= i;j++){
            if(!j) c[i][j] = 1;
            else c[i][j] = (c[i-1][j] + c[i-1][j-1]) % q;
        }
    }
}

ll qmi(ll a,ll b,ll p){
    ll res = 1 % p;
    while(b){
        if(b & 1) res = res * a % p;
        a = (ll)a * a % p;
        b >>= 1;
    }
    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> q;
    init();
    ll sum = 0;
    for(int k = 1;k<=n;k++){
        sum = (sum + c[n][k] * qmi(qmi(2,k,q) - 1,m - 1,q) % q * qmi(2,(m-1) * (n - k),q)) % q;
    }
    cout << sum << endl;

//     system("pause");
    return 0;
}