2024.6.27
T1
题面
给定一个正整数序列 \(a_{1\sim n}\)，以及一个正整数 \(P\)，求有多少的三元组 \((i,j,k)\) 满足:
-
\(1\le i<j<k\le n\)
-
\(P=a_i\times 2^{\lfloor\log_2a_j\rfloor+\lfloor\log_2a_k\rfloor+2}+a_j\times 2^{\lfloor\log_2a_k\rfloor+1}+a_k\)
\(多测，1\le T\le 10^3,1\le n\le 10^5,\sum n\le 10^6,1\le a<2^{20},1\le P\le 2^{60}\)
题解
可以看出，第二个条件本质上是将几个 \(a\) 在二进制的情况下拼起来，可以 KMP 匹配+DP 统计答案，复杂度 \(\mathcal O(\log P\sum n)\)
方法
-
答案角度考虑
答案关心什么，就计算什么。
当答案是在关心一个数二进制下的属性，比如按位与、或、异或运算、1的数量，等等，就应该将数放在二进制下考虑。
以 \(a\) 为底的对数、以 \(a\) 为底数的指数，其实实在考虑 \(a\) 进制的内容
T2
题面
有一个设计失败的机器人，他走路的路线是固定的。
具体地，机器人脑内有一个长度为 \(n\) 的指令序列 \(\{c\},c_i\in\{\text{L},\text{R},\text{D},\text{U}\}\) 分别表示向左、右、下、上走一单位长度。
定义向右为 \(x\) 轴正方向，向上为 \(y\) 轴正方向，假设机器人从 \((0,0)\) 出发，则他会按照这个指令序列走出一条路径。
对于一条路径中的每个点 ，假设这是第 \(i\) 次到达该点，则分数为\(i((|x|+1)\operatorname{xor}(|y|+1))+i\)。一条路径的分数则为该路径上每个点的分数之和。
现在研究人员要删除机器人指令序列中的一个指令。假设删除的是第 \(k\) 个指令。请你对于每个 \(k\) ，求出该机器人按照新的指令序列，从 \((0,0)\) 出发走出的路径的分数。
题解
开始看到异或，想到可能要用在二进制下考虑，但是会发现与题目没有什么关系。
考虑删除一个指令后，终点最多只有 4 种可能。我们从 4 个可能的终点分别倒推出一条路径并维护答案。
在从小到大枚举 \(k\) 的过程中，不断删除路径中的点，更新为正确的点（从前到后走的店）。
时间复杂度 \(\mathcal O(n \log n)\)。期望得分 \(100\) 分。
方法
-
删去操作，应该前后两个方向两头计算，最后合并答案
-
可能状态数思想。去看一个操作，可能总共会带来多少种不同的情况
T3
题面
有一 \(k\) 个物品，其中第 \(i\) 个价值为 \(a_i\)，从中可重且有序地选取 \(n\) 个，求使得价值之和等于 \(m\) 的方案数，对 \(2\) 取模。
\(多测，1\le T\le 10,1\le n\le 10^{18},0\le m\le 10^{18},1\le k\le 200,0\le a_i\le 10^5\)
题解
题目可以抽象为构造一个 \(b\) 序列，求
\[\sum_{\sum_{i=1}^kb_i=n,\sum_{i=1}^ka_ib_i=m}\dfrac{n!}{\prod_{i=1}^kb_i!}\mod 2 \]注意到 \(2\) 取模非常特殊，可以以此入手，考虑答案。
右侧式子对答案产生贡献当且仅当 \(\frac{n!}{\prod_{i=1}^kb_i!}\equiv1\pmod 2\)，因为
\[\frac{n!}{\prod_{i=1}^kb_i!}={n\choose b_1,b_2,\cdots,b_k}={n\choose b_1}{n-b_1\choose b_2}\cdots{n-b_1-b_2-\cdots-b_{k-1}\choose b_k} \]所以其值为一当且仅当后面每一项都为一，根据卢卡斯定理
\[{n\choose b_1}\equiv{n/2\choose b_1/2}{n\bmod 2\choose b_1\bmod 2}\equiv\prod_{bit=0}^{60}{n[bit]\choose b_1[bit]}\pmod 2 \]\(x[bit]\) 值 \(x\) 在二进制下第 \(bit\) 位。
所以在二进制下 \(b_1\subset n\)，同理 \(b_2\subset n-b_1,\cdots, b_k\subset n-b_1-b_2-\cdots-b_{k-1}\)。
所以右面式子值为一，当且仅当：
-
\(\forall 1\le i\le k,b_i\&n=b_i\)
-
\(\forall 1\le i<j\le k,b_i\&b_j=0\)
于是问题转化为，对于 \(n\) 的二进制表示下所有 \(1\) 的位置 \(i\)，选择 \(2^ia_1,2^ia_2,\cdots,2^ia_k\)
之一加入，求最终和为 \(m\) 的方案数。
考虑从低到高枚举每一位，记录和为 \(S\) 的方案数。对于当前的 \(i\)，合法的 \(S\) 满足 \(S ≤2^{i+1}\max a\) 且 \(S\equiv m\pmod {2^i}\)，所以只有 \(\mathcal O(a)\) 个。
但是如果记录 \(dp[i][j]\) 表示考虑前 \(i\) 位时，和为 \(j\) 时的方案，就会导致 \(j\) 非常大，空间根本开不下，根据上面的性质，我们可以设 \(f[i][o]=dp[i][o<<i|(m\&((1<<i)-1)]\)，因为后 \(i\) 位与 \(m\) 相同，不用存，这样空间只需要开到 \(2a\) 级别，加上 bitset 优化
时间复杂度 \(O(\frac{ka \log n}{w}),w=64\)。
方法
-
从小入手——观察数据范围最小的那个变量
-
模 \(a^i\) 可以看作取 \(a\) 进制下前 \(i\) 位，不断进行除模可以看作在 \(a\) 进制下展开
卢卡斯定理就是一种进制展开
-
阶乘除法与组合数之间可以互换
-
组合数可以用卢卡斯定理在模数很小的情况下可以用来推式子或直接求值
-
利用数学性质，避免存储大量无用信息，节省空间。
T4
题面
给定一张 \(n\) 个点 \(m\) 条边的无向图。点的编号为 \(1\) 到 \(n\) ，编号为 \(i\) 的点的权值为 \(a_i\) 。边的编号为 \(1\) 到 \(m\)，编号为 \(i\) 的边连接节点 \(u_i,v_i,|u_i,v_i|\in\{A,B,A+B\}\) 。请你求出这张图的最大带权独立集的权值。
\(3\le n\le 200,1\le m\le 600,1\le A,B<n,1\le 10^6,1\le u_i,v_i\le n\)
题解
方法
- 将一维的数据二维排列