Codeforces Round 940 (Div. 2)
| ID | Difficulty (0-5) | Topic | Status | Code |
|---|---|---|---|---|
| A | 0 | Greedy | Solved | A.cpp |
| B | 0 | Greedy | Solved | B.cpp |
| C | 1 | Counting | Solved | C.cpp |
| D | 2 | XOR, Counting | Solved | D.cpp |
| E | 3 | Math | Upsolved | E.cpp |
| F |
A. Stickogon
显然构造成三角形所需的边数最少。
B. A BIT of a Construction
因为是对所有数的和的限制，所以尽量避免同一位两个数都是 $1$ ，这样“或”的结果和“和”一致。
因此可以把所有有效的 $1$ 都集中到一个数字上，找到最大的 $2^x-1\le k$ 即可。
对 $n=1$ 需要特判。
C. How Does the Rook Move?
注意到如果选的 $(r,c)$ 不同每次同时删掉两行两列，否则删掉一行一列。
先算出来还可以放棋子的行数（或列数）$n’$，然后枚举 $2j$ 个行是被成对删掉的，剩下的都逐个删。
$$
ans =\sum_{0\le j\le \lfloor n’/2 \rfloor} {n’\choose 2j}{2j\choose j}j!=\sum_{0\le j\le \lfloor n’/2 \rfloor}\frac{n’!}{(n’-2j)!j!}
$$
第一个组合数选出来 $j$ 对，第二个选出每个对的第一个元素，然后剩下的 $j$ 个任意排列对应上去。
复杂度 $O(n)$ 。
D. A BIT of an Inequality
给定数列 $a$，定义 $f(l,r)$ 表示区间异或和。
求有多少对 $(x,y,z)$ 满足 $1\le x\le y\le z\le n, f(x,y)\oplus f(y,z)>f(x,z)$ 。
条件是 $f(x, y) \oplus f(y, z)=f(x,z)\oplus a_y>f(x, z)$ ，也就是区间里删一个数异或和变大。
从二进制的角度考虑，假设 $a_y$ 的最高位为 $k$ ，如果 $f(x,z)$ 的第 $k$ 位是 $0$ 则异或后这一位变成 $1$ ，无论更低的位怎么变化，结果都是比之前大的。反之如果 $f(x,z)$ 的第 $k$ 位是 $1$ 则不符合要求。
考虑枚举 $y$ ，统计有多少对合法的 $(x,z)$ ，也就是找一个区间使得异或和在第 $k$ 位上是 $0$ 。
区间转化为两个前缀做差分，记 $sum_i = a_1\oplus a_2\oplus\cdots\oplus a_i$ ，则 $f(x,z)=sum_z\oplus sum_{x-1}$ 。
如果想要 $f(x,z)$ 在第 $k$ 位上是 $0$ ，则 $sum_z$ 和 $sum_{x-1}$ 在第 $k$ 位上应当一致。
令 $pre_{k,0/1}$ 表示 $x<y$ 且 $sum_{x}$ 在第 $k$ 位上是 $0/1$ 的 $x$ 的个数；同理定义 $suf_{k,0/1}$ 表示 $y\le z$ 且 $sum_{z}$ 在第 $k$ 位上是 $0/1$ 的 $z$ 的个数。
那么 $y$ 的贡献就是 $pre_{k,0}\times suf_{k,0}+pre_{k,1}\times suf_{k,1}$ 。
从小到大枚举 $y$ ，可以 $O(\log a)$ 的维护 $pre$ 和 $suf$ ，总复杂度 $O(n\log a)$ 。
E. Carousel of Combinations
$10^5$ 次询问，每次给一个 $n\le 10^6$ ，求
$$
\bigg(\sum_{i=1}^n \sum_{j=1}^i\big(\frac{i!}{(i-j)!j} \bmod j\big)\bigg)\mod 10^9+7
$$
先枚举 $j$ ，然后整理一下：
$$
\sum_{j=1}^n\sum_{i=j}^n \frac{i(i-1)(i-2)\cdots(i-j+1)}{j}\mod j
$$
注意到分子是连续的 $j$ 个数，因此一定恰好有一个 $j$ 的倍数，可以保证能约掉。
除了这个 $j$ 的倍数，剩下的部分模 $j$ 一定是 $1,2,\cdots,j-1$ 。
假设这个 $j$ 的倍数是 $kj$ ，右边的分数可以写成 $k(j-1)!\bmod j$ 。
- 如果 $j$ 是质数，由威尔逊定理 $(p-1)!\bmod p=p-1$，因此等于 $k(j-1)\bmod j$ 。
- 如果 $j$ 是合数，分类讨论：
- 如果 $j$ 不是完全平方数，则存在 $j=ab,1<a,b<j,a\not=b$ ，因此 $a,b$ 都在 $(j-1)!$ 中，有 $k(j-1)!\bmod j = 0$ 因此不管 $i$ 是谁结果恒为 $0$ 。
- 如果 $j$ 是完全平方数，设 $j=x^2$ ，则 $j>4$ 时能保证 $2x<j$ ，此时 $x,2x$ 都在 $(j-1)!$ 中，有 $k(j-1)!\bmod j = 0$ 因此不管 $i$ 是谁结果恒为 $0$ 。对于 $j=4$ 需要特殊处理。
因此我们只需要管 $j$ 为质数以及 $j=4$ 。
对于质数的情况，注意到 $k$ 随着 $i$ 变大的形式是 $j$ 个 $1$，$j$ 个 $2$，$j$ 个 $3$ 等，对应的 $k(j-1)\bmod j$ 就是 $j$ 个 $j-1$，$j$ 个 $j-2$ （即 $2(j-1)\bmod j=j-2$ ），$j$ 个 $j-3$ 等。
对于质数 $j$ 一共会有 $n/j$ 段，因此总段数不会超过调和级数 $O(n\ln n)$ 级别。
考虑同时维护 $n=1,2,\cdots,10^6$ 的答案，维护这些答案的差分数组，那么对于每个质数 $p$ ，在这个差分数组上就是一段一段的区间加，因此维护二阶差分数组就可以 $O(1)$ 支持每段的 update 了。
对于 $j=4$ 操作是一样的，观察一下贡献的形式是四个 $2$ ，四个 $0$ 交替。
做完之后求两遍前缀和就行了，预处理复杂度 $o(n\ln n)$ ，查询复杂度 $O(1)$ 。
Codeforces Round 940 (Div. 2)