2024暑假集训第一周总结

迟来的第一周总结…

第一周一共四场比赛：总的来说还有很多东西没学，或者学的不深，个人感觉八月之前应该在不停的学新东西了，八月之后得对算法加深一些理解和掌握。比赛得时候，签到和能出得思维大家都一样，后期就看谁知识点学过或者掌握的更深了…

牛客多校一：

这一场补了三个题

A-A Bit Common_2024牛客暑期多校训练营1 (nowcoder.com)

$题意是给你n(n\le5000),m(m\le5000),q(q\le10^9)三个数,求从[0,2^m)任取数凑成长度为n的序列，并且该序列中存在一个子$

$序列AND值为1，求总共的方案数并对\ q \ 取模。$

$分析：$

$n,m都是5000，显然时间复杂度在o(n^2)以内，所以我们可以考虑枚举子序列的个数$

$假设子序列为k个 那么有c(n,k)种序列位置可能$.

$一个数AND为1 只能为1$

$多个数AND值为1，那么他们的2进制位最低位一定为1，其他位一定都不同时为1 $

$剩下的n-k个就随便选了 .$

$总结一下就得出一个公式：$

$\sum_{k=2}^{n} C(n,k)(2^k-1)^{m-1}2^{(m-1)(n-k)}$

$组合数预处理用递推式o(n^2)，枚举序列计算答案为o(nlogm),总时间复杂度为o(n^2)$

总结：题不难，也没用到的什么难的知识点 还是组合数论推式子类题刷的少

B-A Bit More Common_2024牛客暑期多校训练营1 (nowcoder.com)

题意和范围跟上面一样，区别是找到序列中存在两个子序列AND值为1方案数

分析：