E.Arena (Educational Codeforces Round 116)

E.Arena

题目大意，一共有 nn 个人战斗，每个人初始时有 aia_i 的 HP，但是 aia_i 未知，只知道 1⩽ai⩽x1 \leqslant a_i \leqslant x
如果一个人的 HP <1< 1，那么这个人死亡，每一轮攻击，一个活着的人会向其他所有人发动一次攻击，消减 1 HP1 \ \text{HP}
最后活着的人取得胜利，现在问，如果最后没有人活下来，此时 aia_i 有多少种选法？

分析
注意问题中的条件，一轮攻击下来，只要是活着的人，会向其他所有人发动削减 1 HP1 \ \text{HP} 的攻击
如果一个人在一轮攻击中死去，假设这一轮有 ii 个人活着，那么这一个人所承受的攻击 Δ∈[1,i−1]\Delta \in [1, i-1]
换句话说，血量 ⩽i−1\leqslant i-1 的，都会死亡

根据这个就可以设计状态了，假设攻击前有 ii 个人存活，每个人最多能承受的攻击数量为 jj，这时候的方案数为 dp(i,j)dp(i, j)
那么一轮攻击下来，只剩下 kk 个人存活，这 kk 个人最多必须能承受 nj=min⁡(x,j+(i−1))nj = \min(x, j+(i-1)) （题目要求上界为 xx）
那么接下来考虑 dp(i,j)→dp(k,nj)dp(i, j) \to dp(k, nj) 的转移，大致为 dp(k,nj)+=dp(i,j)⋅Qdp(k, nj) += dp(i, j) \cdot Q，QQ 为这一轮死掉的 i−ki-k 个人的情况

考虑 QQ，这一轮死掉的 i−ki-k 个人，每个人的血量取值范围为 [1,nj−j][1, nj-j]，注意不能写成 [1,i−1][1, i-1]，因为有上界 xx 的限制
Q=(ii−k)⋅(nj−j)i−kQ = \displaystyle\binom{i}{i-k} \cdot (nj-j)^{i-k}

枚举 i,ki, k，枚举 j∈[0,x]j \in [0, x]

dp(k,nj)+=dp(i,j)⋅(ii−k)⋅(nj−j)i−k,(k<i, nj=min⁡(x,j+(i−1)))dp(k, nj) += dp(i, j) \cdot \binom{i}{i-k} \cdot (nj-j)^{i-k}, \quad (k < i, \ nj = \min(x, j+(i-1)))

递推的时候，合法方案才发生转移，dp(i,j)=0dp(i, j) = 0 为非法方案
初始状态为 dp(n,0)=1dp(n, 0) = 1，最后的答案为 ans=∑j=0xdp(0,j)ans = \displaystyle\sum_{j = 0}^{x} dp(0, j)

注意转移的时候 dp(i,j)dp(i, j)，i=[n→2]i = [n \to 2]，因为仅有 11 个人存活是非法状态

Educational Codeforces Round 116 其他题目
C. Banknotes

题目大意转换为 10a1⋅x1+10a2⋅x2+⋯10an⋅xn=S10^{a_1} \cdot x_1 + 10^{a_2} \cdot x_2 + \cdots 10^{a_n} \cdot x_n = S
其中给定 x1+x2+⋯xn=k+1x_1 + x_2 + \cdots x_n = k+1，求 SS 的最小值

首先来看一个贪心策略，x1x_1 最多能拿多少呢？因为 10a2=10a1⋅10a2−a110^{a_2} = 10^{a_1} \cdot 10^{a_2 - a_1}
也就是说，现在 S=10a2S = 10^{a_2}，如果我用 10a2−a110^{a_2 - a_1} 张票去表示 SS 是不划算的
我用 11 张 10a210^{a_2} 就可以表示 SS 了，用 10a2−a110^{a_2 - a_1} 这么多就是浪费

根据贪心策略，x1,x2,⋯x_1, x_2, \cdots 要尽可能多，然后后面几项 ⋯xn\cdots x_n 都填 00 即可
x1x_1 最多可以为 (10a2/10a1)−1(10^{a_2}/10^{a_1})-1，以此类推，令 xi=10ai+110ai−1x_i = \displaystyle\frac{10^{a_{i+1}}}{10^{a_i}}-1

这样就可以设计出如下算法，令 res=k+1, S=0res = k+1, \ S = 0
对于每一个 ii，如果 res⩾xires \geqslant x_i，则 S+=10ai⋅xi, res−=xiS += 10^{a_i}\cdot x_i, \ res -= x_i
否则 S+=res⋅10ai, res=0S += res \cdot 10^{a_i}, \ res = 0，当 res⩽0res \leqslant 0 的时候退出循环

Codeforces Round 752 (Div. 1)

F. October 18, 2017

题目大意，给你三个数 n,k,xn, k, x，求满足以下条件的序列个数
假设序列为 {a1,a2,⋯an}\{a_1, a_2, \cdots a_n\}，其中序列的长度必须为 nn，此外

  • 对于每个 ii，有 0⩽ai<2k0 \leqslant a_i < 2^k
  • 这个序列的任意非空子序列（不一定连续），子序列元素的异或和都不等于 xx
    说明，这里的 aia_i 可以相同

简单情况，此时 x=0x = 0
若 n>kn > k，这样的序列一定不存在，返回 00 即可，因为要想任意子序列的异或和都不为 00，只能如下构造

A=(00⋯0100⋯10⋱⋮10⋯00)A = \begin{pmatrix} 0 & 0 & \cdots & 0 & 1 \\ 0 & 0 & \cdots & 1 & 0 \\ & \ddots & \vdots \\ 1 & 0 & \cdots & 0 & 0 \end{pmatrix}

（即对角线为 11 的单位矩阵），只能有 kk 个元素，如果再多放进去一个元素 uu
不管这个元素哪一位为 11，或者多个位为 11，总可以从 AA 中找到相应的 aia_i，使得相应的位异或为 00

下面只需考虑 n⩽kn \leqslant k，x=0x = 0 的情况
那么构造的方式类似线性基，对于 kk 位的向量空间，dim=k\text{dim} = k，一共有 2k−12^{k} - 1 个非 00 向量
假设已经构造出的元素是 {a1,a2,⋯ ,ai−1}\{a_1, a_2, \cdots, a_{i-1}\}，考虑构造 aia_{i}
类似线性基，需要保证低位 [0⋯i−1][0\cdots i-1]位可以自由选择，高位 [i⋯k][i \cdots k] 必须出现一个 11
此时低位已经在 {a1,a2,⋯ai−1}\{a_1, a_2, \cdots a_{i-1}\} 构造的过程中，计算了方案数，答案为

A(i−1)=(00⋯0100⋯10⋱⋮11⋯11) \displaystyle \bm{A}(i-1) = \begin{pmatrix} 0 & 0 & \cdots & 0 & 1 \\ 0 & 0 & \cdots & 1 & 0 \\ & \ddots & \vdots \\ 1 & 1 & \cdots & 1 & 1 \end{pmatrix} ，其中 A(i−1)\bm{A}(i-1) 表示向量有 i−1i-1 位

那么此时 aia_i 的选择，只能是从 (>(11⋯1)i−1)(> (11 \cdots 1)_{i-1}) 开始选，也就是剩下的
cnt(i)=A(k)−A(i−1)=(2k−1−(2i−1−1))=2k−2i−1cnt(i) = \bm{A}(k) - \bm{A}(i-1) = (2^{k}-1 - (2^{i-1} - 1)) = 2^{k} - 2^{i-1} 个选择

综上所述，{a1,a2,⋯ ,an}\{a_1, a_2, \cdots, a_n\} 一共有 ∏i=1ncnt(i)\displaystyle \prod_{i = 1}^{n} cnt(i) 种
答案为 (2k−1)⋅(2k−21)⋅(2k−22)⋯⋅(2k−2n−1)(2^{k}-1)\cdot (2^{k}-2^1) \cdot (2^{k}-2^2) \cdots \cdot (2^{k} - 2^{n-1})

考虑 x⩾1x \geqslant 1 的情况

首先注意到本例是统计方案，如果已经统计出任意子序列异或和在第 ii 位不为 11 的方案数
那实际上方案数和这个 11 出现在第几位是没有关系的，由此可以推出一个结论，对于 x≠0x \neq 0 而言
所有 x>1x > 1 的方案数等价于 x=1x = 1 的方案数，这可以通过映射来证明

首先对于所有 x>1x > 1 的方案，我们可以取 highbit(x)\text{highbit}(x)，将 11 从最高位换到最低位
子序列的异或和不为 xx，那么在 highbit(x)\text{highbit}(x) 位异或和也一定不为 11，这样的方案数可以映射到 x=1x = 1 的方案数
其次对于所有 x=1x = 1 的方案，我们可以将这个 11 调整到 [1⋯k][1\cdots k] 的任意一位
这样每一个 x=1x = 1 的方案可以构造出任意 1<x<2k1 < x < 2^{k} 的方案，下面只需考虑 x=1x = 1 的情况

不妨用 P(i)P(i) 表示 hightbit(x)=i\textbf{hightbit}(x) = i （即最高为 11 的位是第 ii 位），[i−1⋯0][i-1 \cdots 0] 位为自由变量
（自由变量就是可以为 00 也可以为 11），此时满足条件的方案数（条件指的是：任意子序列的异或和都不为 11）
其中， i∈[k−1→0]i \in [k-1 \to 0]

最后的答案为 ∑i=k−1→0P(i)\displaystyle \sum_{i = k-1 \to 0} P(i)，下面考虑如何计算 P(i)P(i)

从线性基的角度来考虑问题，P(i)P(i) 对应的方案中，第 ii 位为 11，此时 {a1,a2,⋯an}\{a_1, a_2, \cdots a_n\} 构成的解空间方案数记为 S(i)S(i)
第 ii 位为 11，对应的解空间 S(i)S(i) 的维度 dim(S)=i\textbf{dim}(S) = i

下面考虑维度为 tt 的解空间，记为 S(t)=(x(t):00⋯01 00⋯10  ⋱⋮ 11⋯11)\bm{S}(t) = \begin{pmatrix}\bm{x}_{(t)}: & 0 & 0 & \cdots & 0 & 1 \\ \ & 0 & 0 & \cdots & 1 & 0 \\ \ & \ & \ddots & \vdots \\ \ & 1 & 1 & \cdots & 1 & 1\end{pmatrix}

其中 x(t)\bm{x}_{(t)} 表示向量的维度为 tt，下面考虑 S(t)S(t) 可以由 11 张成和不能由 11 张成的方案数

如果 S(t)S(t) 可以由 11 张成，换句话说 S(t)S(t) 中含有向量 1\bm{1}，也就是说 SS 必须为

(0⋯01  ⋯0   ⋯0 ⋱⋮  ⋯0)\displaystyle\begin{pmatrix} 0 & \cdots & 0 & 1 \\ \ & \ & \cdots & 0 \\ \ & \ & \cdots & 0 \\ \ & \ddots & \vdots \\ \ & \ & \cdots & 0\end{pmatrix} 这样的形式，才能保证选取任意子项进行高斯消元，1\bm{1} 这一项不会被消去

也就是说，span(1)\textbf{span}(1) 的方案数为和 1\bm{1} 线性无关，或者说正交的向量个数，这样的向量有多少个呢？

实际上我们除了 1=(0 0⋯ 0 1)\bm{1} = (0 \ 0 \cdots \ 0 \ 1) 这个向量外，要在 S(t)S(t) 中选出低位为 00 的非 00 向量，与 11 构成线性组合
S(t)\bm{S}(t) 数的取值范围为 [1⋯2t−1][1\cdots 2^{t}-1]，也就是对应 2t−12^{t}-1 个非 00 向量
其中最低位为 00 的数一共有 2t−1−12^{t-1} - 1 个，最低位为 11 的数有 2t−12^{t-1} 个，由此可以推出以下结论

结论 1，对于 S(t)\bm{S}(t)，包含 1\bm{1} 的子空间有 span(1)=2t−1−1\textbf{span}(1) = 2^{t-1} - 1 个，不包含 11 的有 span(≠1)=2t−1\textbf{span}(\neq 1) = 2^{t-1} 个

对于维度为 ii 的空间 S(i)S(i) 计算 P(i)P(i)

基本的思想是，先计算 kk 维解空间中能划分出多少个 ii 维子空间？然后再在这个子空间中任意选择 nn 个作为 {a1,⋯ ,an}\{a_1, \cdots, a_n\}

P(i)P(i) 不太好直接计算，因为解空间的维度 k⩾ik \geqslant i，[i−1→0][i-1 \to 0] 这几位为自由变量，并且不能包含 1\bm{1}
这部分很好计算，就是 2i−12^{i-1} 种
那么 [k−1→i][k-1 \to i] 这几位呢？我们要的 P(i)P(i) 是 highbit(x)=i\textbf{highbit}(x) = i，只是其中的 11 位
更高位 [i+1→k][i+1 \to k] 的情况该怎么考虑？

我们想到利用容斥间接计算 P(i)P(i)，定义 Q(i)Q(i) 如下
Q(i)Q(i): 高 ii 位子空间，即 [k−1→k−i][k-1 \to k-i] 包含 1\bm{1}，同时低 k−ik-i 位子空间
即 [k−i−1→0][k-i-1\to 0] 为自由变量，这样的子空间划分的方案数记为 Q(i)Q(i)（自由变量就是可为 00 可为 11）

这样对于 i∈[0→k−1]i \in [0\to k-1]，根据容斥原理，P(i)=Q(i)−Q(i+1)+Q(i+2)−⋯+(−1)k−1−iQ(k−1)P(i) = Q(i) - Q(i+1) + Q(i+2) - \cdots + (-1)^{k-1-i} Q(k-1)
752div1-f

这样高 ii 位的方案数 high(i)\textbf{high}(i) 为 dim(k−i+1)⋅dim(k−i+2)⋯⋅dim(k)dim(k-i+1) \cdot dim(k-i+2) \cdots \cdot dim(k)，其中 dim(i)dim(i) 表示维度为 ii 的子空间
包含向量 1\bm{1} 的方案数
high(i)=(2(k−1)−(i−1)−1)⋅(2(k−1)−(i−2)−1)⋯(2k−1−1)=∏j=0i−1(2k−1−j−1)\textbf{high}(i) = (2^{ (k-1)-(i-1) } - 1) \cdot (2^{ (k-1)-(i-2) } - 1) \cdots (2^{k-1} - 1) = \displaystyle\prod_{j = 0}^{i-1}(2^{ k-1-j } - 1)

低 k−ik-i 位的方案数为 2k−i−12^{k-i-1}，别忘了低 k−ik-i 位对应 k−ik-i 维空间放置自由变量
对于 {a1,a2,⋯ ,an}\{a_1, a_2, \cdots, a_n\}，每一项都有 2k−i2^{k-i} 种选择，所以还要乘上 (2k−i)n(2^{k-i})^n

构造子空间的过程具体如下，k−ik-i 维子空间有 2k−i2^{k-i} 个向量，其中 2k−i−12^{k-i-1} 个末尾为 00，2k−i−12^{k-i-1} 个末尾为 11
末尾为 00 的向量可以任意选择，来张成低位的 k−ik-i 维子空间，有 2k−i−12^{k-i-1} 种选择
这些向量填充了子空间的一半，并且它们的高位 [k−i,k−i+1,⋯ ,k−1][k-i, k-i+1, \cdots, k-1] 是 00
剩下的一半怎么构造？
如图所示，在原来低 k−ik-i 维的基础上，往外扩 11 位，让这一高位填上 11，构成 k−i→k−i+1k-i \to k-i+1 维的递推
这样第 k−i+1k-i+1 维空间中含有 1\bm{1} 的方案数恰为 2k−i−12^{k-i} - 1，以此类推
最后这部分的方案数为 (2k−i−1)⋅(2k−i+1−1)⋯(2k−1−1)(2^{k-i} - 1) \cdot (2^{k-i+1} - 1) \cdots (2^{k-1} - 1)
同时构造出 {a}\{a\} 每一项可能的取值有 2k−i2^{k-i} 种

于是有如下结论
结论 2，在 kk 维空间中，划分出低位对应的 k−ik-i 维子空间，放自由变量，同时剩下的高位 ii 维空间放置向量 1\bm{1} 张成的子空间
这样的方案数 Q(i)=(∏j=0i−12k−1−j−1)⋅(2k−1−i)⋅(2k−i)nQ(i) = \displaystyle\left( \prod_{j = 0}^{i-1} 2^{k-1-j} - 1 \right) \cdot (2^{k-1-i}) \cdot (2^{k-i})^{n}

kk 阶容斥计算答案

容斥原理 集合 SS 中至少具有性质 P1,P2,⋯PmP_1, P_2, \cdots P_m 之一的对象个数由如下给出

∣A1∪A2∪⋯∪Am∣=∑∣Ai∣−∑∣Ai∩Aj∣+∑∣Ai∩Aj∩Ak∣−⋯+(−1)m+1∣A1∩A2∩⋯∩Am∣\begin{aligned} |A_1 \cup A_2 \cup \cdots \cup A_m| &= \sum |A_i| - \sum |A_i \cap A_j| + \sum |A_i \cap A_j \cap A_k| - \cdots \\ &+ (-1)^{m+1} |A_1 \cap A_2 \cap \cdots \cap A_m| \end{aligned}

其中 AiA_i 为具有性质 PiP_i，也可能有其他性质的对象构成的子集

回到本问题，定义 P(i)P(i) 为如下性质
在 kk 维空间内，k−ik-i 维作为低位放置自由变量，这些划分空间构成的集合记为 P(i)P(i)

可以推出 ∑i=0k−1∣Ai∣=Q(0)\displaystyle\sum_{i = 0}^{k-1} |A_i| = Q(0)，∑i,j∈[0,k−1]∣Ai∩Aj∣=Q(1)\displaystyle \sum_{i, j \in [0, k-1]} |A_i \cap A_j| = Q(1)，以此类推
∣A0∩A1∩⋯∩Ak−1∣=Q(k−1)|A_0 \cap A_1 \cap \cdots \cap A_{k-1}| = Q(k-1)

具体来说，Q(0)∩Q(1)=Q(1)Q(0) \cap Q(1) = Q(1)，因为 kk 维的方案中肯定统计了 k−1k-1 维的方案
而 k−1k-1 维的方案又包含了 k−ik-i 维的方案，1<i⩽k−11 < i \leqslant k-1，所以 ∑i,j∣Ai∩Aj∣=Q(1)\displaystyle\sum_{i, j} |A_i \cap A_j| = Q(1)

kk 阶容斥之后的结果为

tot=Q(0)−Q(1)+Q(2)−⋯+(−1)k−1Q(k−1)tot = Q(0) - Q(1) + Q(2) - \cdots + (-1)^{k-1} Q(k-1)

代入之后结果为

(2k−1⋅(2k)n)−( (2k−1−1)⋅2k−2⋅(2k−1)n )+( (2k−1−1)(2k−2−1)⋅2k−3⋅(2k−2)n )+⋯+(−1)k−1⋅(2k−1−1)(2k−2−1)⋯(21−1)⋅20⋅(21)n\begin{aligned} \left( 2^{k-1} \cdot (2^{k})^n \right) &- \left(\ (2^{k-1}-1) \cdot 2^{k-2}\cdot (2^{k-1})^n \ \right) + \left(\ (2^{k-1}-1)(2^{k-2}-1) \cdot 2^{k-3} \cdot (2^{k-2})^n \ \right) \\ &+\cdots +(-1)^{k-1} \cdot (2^{k-1}-1)(2^{k-2}-1)\cdots (2^1-1) \cdot 2^0 \cdot (2^1)^n \end{aligned}

可以简写为

∑i=0k−1(−1)i⋅(2k−i)n⋅(∏j=0i−1(2k−1−j−1))⋅2k−1−i\sum_{i = 0}^{k-1} (-1)^{i} \cdot (2^{k-i})^n \cdot \left(\prod_{j = 0}^{i-1}(2^{k-1-j} - 1)\right) \cdot 2^{k-1-i}