2024牛客多校第一场——A Bit Common 题解

一、题目描述

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

二、解题思路

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

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

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

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

综上所述，枚举 $k$ ，求解答案，表达式为： $C_{n}^{k} \cdot C_{n - k}^{n - k} \cdot 2^{(m - 1) \cdot (n - k)} \cdot (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;
}

一、题目描述

二、解题思路

三、AC代码

分享到微信

发送评论 编辑评论

发送评论编辑评论