Chef and Proxy - PROXYC
题目描述
给定一个由字符 $A,P$ 构成序列 $S$
你可以把一些位置上的值变成 $B$，如果 $S_i$ 能变成 $B$，当且仅当：
- $3 \le i \le n-2$
- $S_i=A$
- $([S_{i-1}=P] \lor [S_{i-2}=P]) \land ([S_{i+1}=P] \lor [S_{i+2}=P])$
你的目标是把尽可能少的 $A$ 变成 $B$，之后需要满足 $ \frac{\sum_{x \in S}[x \ne A]}{|S|} \ge \frac{3}{4}$
数据范围：$1 \le |S| \le 1000$
题解
设有 $x$ 个位置可以变成 $B$，有 $y$ 个位置是 $P$，至少需要 $z$ 个非 $A$ 的位置
如果 $y \ge z$，那么就直接可行了，否则需要 $z-y$ 个位置放 $B$，判断一下即可
Guddu on a Date - KS2
题目描述
定义圆数为十进制下个位数字之和为 $10$ 的倍数的正整数，求第 $n$ 个圆数
数据范围：$1 \le n \le 10^{18}$
题解
首先圆数的位数不会小于 $2$，而且个位是由个位前的数位之和唯一确定的
也就是所有圆数去掉个位后互不相同，且构成正整数集
也就是只需要输出 $n \cdot 10+((10-m \bmod 10) \bmod 10)$ 即可，其中 $m$ 为 $\left\lfloor \frac{n}{10} \right\rfloor$ 的各个数位之和
Road Signs - RSIGNS
题目描述
$Marichka$ 在去大厨国的途中看到了 $10^K$ 个路牌（编号为 $0 \sim 10^K-1$）
编号为 $i$ 的路牌一面写了数字 $i$，另一面写了数字 $10^K − i − 1$
$Marichka$ 想知道，有多少块路牌正反两面的数字中，一共只有两种不同的数位？
由于答案可能很大，请求出其对 $10^9 + 7$ 取模的结果
数据范围：$1 \le K \le 10^9$
题解
显然答案就是 $10 \times 2^{K-1}$
Chef and Ingredients - CHFING
大厨想要做一顿满汉全席，为此，他需要各种各样的食材
每种食材都有自己的美味程度，可以是任意正整数
初始时，对于 $[K, K + N − 1]$ 内的每种美味程度，大厨都有无限量的食材
食材有个独特的性质：任意两种食材经过混合，都可以得到一种新食材
设原本两食材的美味程度分别为 $x$ 和 $y$，那么新食材的美味程度就是 $x + y$
混合得到的新食材也可以再次被混合，大厨可以以任意方式混合任意多次
如果无论如何都无法得到美味程度为 $v$ 的食材，那么我们称美味程度 $v (v > 0)$ 是不可达成的
否则，就是可达成的
大厨要做出每种可达成的美味程度的食材，因此他想知道有多少种不可达成的美味程度
由于种数可能很多，请你求出其对 $10^9 + 7$ 取模的结果
注：可达成美味程度有无穷多种，但可以证明对于 $N \ge 2$，不可达成的美味程度一定只有有
限种
数据范围：$2 \le N \le 10^{18},1 \le K \le 10^{18}$
题解
设你能使用的数字为 $a,a+1,a+2,\cdots,b$，那么 $1 \sim a-1$ 一定无法达成
如果 $b \ge 2a$，则所有数字都可以构成
否则 $b+1 \sim 2a$ 是无法构成的，把 $[a,2a]$ 当作一块，所有块的 $b+1 \sim 2a$ 部分都无法构成
于是答案就是：
$$
\sum_{i=0}^{K+N-3}\left\lfloor \frac{i}{N-1} \right\rfloor
$$
Sum and GCD - SUMAGCD
题目描述
大厨有一个正整数序列 $A_1, A_2, \cdots , A_N$
他想要将这个序列分成两个非空的（未必连续的）子序列 $B$ 和 $C$，使得 $\gcd(B) + \gcd(C)$ 尽可能大
请你求出这一最大值
数据范围：$2 \le N \le 10^5, 1 \le A_i \le 10^9$
题解
首先重复的数字是没用的，先去重一下
猜想最优解一定是某个数单独作为一个集合，剩下的数字另作一个集合
然后写一下，发现它过了
Lent Money - LENTMO
题目描述
大厨借了些钱给 $Chefexim$
大厨讨债讨了好一阵子了，但 $Chefexim$ 总是能找到一些理由拖着
这次，大厨真的生气了，他自己想做点印度点心都没钱买食材了
看到大厨这么生气，$Chefexim$ 终于决定还钱了
他知道大厨喜欢做题，因此还钱的同时还送了大厨一道题，让他消消气
$Chefexim$ 把借来的钱分装进了 $N$ 个袋子（编号为 $1 \sim N$），第 $i$ 个袋子里有 $A_i$ 块钱
他把所有 $N$ 个袋子都给了大厨，然后告诉了他两个整数 $K$ 和 $X$
大厨可以任意次（包括零次）进行下面的操作：
- 选择 $K$ 个不同的袋子，编号分别为 $i_1, i_2, \cdots , i_K (1 \le i_j \le N)$
- 改变选择的袋子里装的金额，对于 $1 \le j \le K$，编号为 $i_j$ 的袋子里的钱从 $A_{i_j}$ 变为 $A_{i_j} \text{ xor } X$
每个袋子可以在任意多次操作中被选择
假设大厨按照最优策略操作，最后所有袋子里的金额之和最大可以是多少？
数据范围：$1 \le N \le 10^4, 1 \le K \le N, 0 \le A_i \le 10^9, 0 \le X \le 10^9$
题解
首先题意可以转化为，给定 $n$ 张牌，每张牌正面是 $0$，反面是 $b_i$
每次你可以选择 $k$ 张牌并把它们翻面，最大化最终所有牌朝上面的数字之和
首先如果 $k=n$ 可以特判掉
否则，如果 $k$ 是奇数，则可以把任意多张牌都翻面
如果 $k$ 是偶数，则只能把任意偶数张牌翻面
那么从大到小排序后贪心即可
Intersecting Paths - INTRPATH
题目描述
给定一棵 $N$ 个节点的树（无向无环连通图），节点编号为 $1 \sim N$
对于每对节点 $u$ 和 $v$，记它们之间的简单路径为 $(u, v)$
这些路径都是没有方向的，因此 $(u, v)$ 与 $(v, u)$ 等价
你需要回答 $Q$ 个询问，每个询问给定两个节点 $u$ 和 $v$
对于树中每一条简单路径 $(a, b)$，我们定义完美相交如下：
- 记路径 $(u, v)$ 和 $(a, b)$ 途经的节点（包括端点）集合分别为 $S_1$ 和 $S_2$
- 如果 $|S_1 \cap S_2|=1$（即两条路径只有一个公共节点），那么 $(a, b)$ 与 $(u, v)$ 完美相交
询问的回答即与 $(u, v)$ 完美相交的简单路径条数
数据范围：$1 \le Q \le 3 \cdot 10^5,1 \le u,v \le N \le 250000$
题解
只需要对于每个链上的点考虑一下经过它的路径条数即可
设 $s_u$ 表示 $u$ 的子树大小，$f_u$ 表示 $u$ 的子树中经过 $u$ 的路径条数，考虑链上的边 $u \to v$，那么交点为 $u$ 的路径条数为 $f_u-s_v(s_u-s_v)$，预处理后前缀和即可解决
之后特殊考虑一下 $\text{lca}$ 处的答案即可
Chef and His Dish - COOLCHEF
题目描述
大厨在厨房里做实验
他有 $N$ 种香料（编号为 $0 \sim N − 1$），类型分别为 $S_0, S_1 , \cdots, S_{N−1}$
你需要回答 $Q$ 个询问，每个询问给定两个整数 $L$ 和 $R$
大厨想使用编号在 $[L, R]$ 中的所有香料来做一道菜
不过，大厨不知道应该以什么顺序放这些香料
因此，他想知道一共有多少种不同的可能
即，序列 $S_L, S_{L+1}, \cdots , S_R$ 共有多少本质不同的排列方案
由于答案可能很大，请输出答案对 $10^9 + 7$ 取模的结果
我们认为两种排列本质不同，当且仅当存在下标 $i$，且两个排列的第 $i$ 位不同
你需要在线回答所有询问，输入已经过加密
数据范围：$1 \le N,Q \le 3 \cdot 10^5, 1 \le S_i \le 10^9, 0 \le L, R < n$
题解
分块模板题，卡卡常就过了
Count Arrays - COUNTIT
题目描述
考虑所有仅包含 $[1, K]$ 中的整数的 $N$ 行 $M$ 列矩阵（行列均从 $1$ 开始编号）
对于每个这样的矩阵 $A$，按下述规则构造序列 $L_1, L_2, \cdots , L_{N+M}$：
- 对于 $1 \le i \le N$，$L_i$ 为 $A$ 第 $i$ 行中元素的最大值
- 对于 $1 \le i \le M$，$L_{i+N}$ 为 $A$ 第 $i$ 列中元素的最大值
请求出有多少种不同的序列，由于答案可能很大，请输出其对 $10^9 + 7$ 取模的结果
数据范围：$1 \le K\ le 10^9, 1 \le N,M \le 10^5$
题解
猜想这个序列只需要满足前 $n$ 个位置和后 $m$ 个位置的最大值相同即可
不难得到答案为：
$$
\begin{aligned}
\sum_{x=1}^{k} \left(x^n-(x-1)^n\right) \left( x^m-(x-1)^m \right)
\end{aligned}
$$
至多是个 $n+m+10$ 次多项式，暴力插值即可
另一个没法做的想法：
定义 $0^0=1$，答案为：
$$
\begin{aligned}
&\sum_{x=1}^{k} \sum_{i=1}^{n} {n \choose i} (x-1)^{n-i} \sum_{j=1}^{m} {m \choose i} (x-1)^{m-j} \\
=&\sum_{x=1}^{k} \sum_{i=0}^{n-1} {n \choose n-i} (x-1)^{i} \sum_{j=0}^{m-1} {m \choose m-i} (x-1)^{j} \\
=&\sum_{x=1}^{k} \sum_{i=0}^{n-1} {n \choose i} (x-1)^{i} \sum_{j=0}^{m-1} {m \choose i} (x-1)^{j} \\
=&\sum_{i=0}^{n-1}\sum_{j=0}^{m-1} {n \choose i} {m \choose j} \sum_{x=1}^{k} (x-1)^{i+j} \\
=&\sum_{i=0}^{n-1}\sum_{j=0}^{m-1} {n \choose i} {m \choose j} \sum_{x=0}^{k-1} x^{i+j} \\
=&\sum_{i=0}^{n-1}\sum_{j=0}^{m-1} {n \choose i} {m \choose j} f_{i+j}(k) \\
=&\sum_{T=0}^{n+m-2}f_T(k) \sum_{i=0}^{T} {n \choose i} {m \choose T-i}[i<n][T-i<m] \\
=&\sum_{T=0}^{n+m-2}f_T(k) \left({n+m \choose T}-{m \choose T-n}-{n \choose T-m} \right)
\end{aligned}
$$
其中 $f_T(k)=\sum_{i=0}^{k-1}i^T$
然而这个玩意不太能做，还是算了
