2024牛客暑期多校训练营1 A题解题思路

前言：

今年和队友报了牛客暑期多校比赛，写了一下午结果除了签到题之外只写出了一道题（A），签到题没什么好说的，其他题我也没什么好说的（太菜了，根本写不出来），这道题能经过自己推导写出公式其实也蛮有成就感的。

正文：

思路：

题目大意主要是让你从0-2^m中选出长为n的序列（可重复，顺序不同算不同序列），这个序列要求有一子序列按位与的结果为1（注意如果子序列为{1}那么也算满足情况），让你输出可以满足此情况的序列总个数对q取模的结果。

其实这是一道彻彻底底的数学题，只要能把公式推出来其实代码很好实现，重点在于公式的推导。（这公式我还想了蛮久）

对于一些数，要想他们按位与的结果为1，也就是结果二进制表示为……0000000000001（总位数为m），那么这一段数的最后一位就必须都为1，并且其他位的按位与结果都必须为0（对于二进制的其中一位这n个数至少得有一个数的这一位为0，也就是不能出现全为1的情况，总数为 $2^{n}-1$ ）。根据这种情况，我们可以知道这段序列的情况共有 $(2^{n}-1)^{m-1}$ 种，很显然这个序列的所有长度大于1的子序列都是满足条件的，这是最完美的情况，但是我们满足条件的子序列只需一个就行了，所以我们可以对这个完美序列进行改数，比如对其中某一个数更改为二进制第一位为0的任意数，更改完之后的序列依旧满足条件（存在满足条件的子序列），这时序列的种类数经分析得知为 $(2^{n-1}-1)^{m-1}*(2^{m-1})*C_{n}^{1}$ ，这是对一个数进行更改的情况，我们还能对更多的数进行更改如此可以知道最终结果为 $\sum_{0}^{n-1}(2^{n-i})^{m-1}*(2^{m-1})^{i}C_{n}^{i}$ 。最后一边加和一边取余即可得出答案。

注意这边求组合数取模时不能用扩展欧几里得或费马小定理（这两个公式前者要求两数互质，后者要求模数为质数），这边由于模数是未知的所以得用递推公式求解，

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,mod;
ll fact[5005];
ll quickpow(ll base,ll power){//快速幂
	ll ret=1;
	while(power){
		if(power%2) ret=ret*base%mod;
		base=base*base%mod;
		power/=2;
	}
	return ret;
}
void init(){ 
	fact[0]=1;
	for(long long i=1;i<=n;i++)fact[i]=fact[i-1]*i%mod;
	
}
int c[5005][5005];
void init2(){
    for(int i = 0;i<=n;i++)
        for(int j =0;j<=i;j++)
            if(!j)c[i][j]=1;//规定 a 0 = 1
            else c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
}
int main(){
	cin>>n>>m>>mod;
	init();init2();
	ll res=quickpow(2,m-1);
	ll ans=0;
	for(int i=0;i<n;i++){
		ans+=((quickpow((quickpow(2,n-i)-1),m-1)%mod*quickpow(res,i)%mod)*c[n][i])%mod;
		ans=ans%mod;
		//cout<<quickpow((quickpow(2,n-i)-1),m-1)<<" "<<quickpow(res,i)<<" "<<C(i,n)<<endl;
		//cout<<ans<<endl;
	}
	cout<<ans<<endl;
	return 0;
}