Sol

设 $c_i(0\le i\le 9)$ 表示 $i$ 这个数字在 $k$ 中出现了几次，则

$$\begin{aligned} Ans &= \sum_{k=1}^X \sum_{i=1}^9 i \cdot \frac{10^{\sum_{j=i}^9 c_j}-10^{\sum_{j=i+1}^9 c_j}}{9}\\ &= \sum_{k=1}^X \sum_{i=1}^9 \sum_{y=1}^i \frac{10^{\sum_{j=i}^9 c_j}-10^{\sum_{j=i+1}^9 c_j}}{9}\\ &= \sum_{k=1}^X \sum_{y=1}^9 \sum_{i=y}^9 \frac{10^{\sum_{j=i}^9 c_j}-10^{\sum_{j=i+1}^9 c_j}}{9}\\ &= \sum_{k=1}^X \sum_{y=1}^9 \frac{10^{\sum_{j=y}^9 c_j}-1}{9}\\ \end{aligned}$$

在最外层枚举 $y$ 之后，可以用数位 dp 在 $O(\lg^2 X)$ 的时间内算出答案。

简单转化之后（可以参考官方题解），变成了：网格中有个阶梯形状的轮廓线，棋子从 $(0,0)$ 开始走，每次可以往左走或者往上走，走到边界的那一步的操作者输（即，边界上的点是必胜态）。

可以证明，如果 $(x+1,y+1)$ 不在边界上，那么 $(x,y)$ 的胜负状态和 $(x+1,y+1)$ 的胜负状态相同。

证明：

Sol

分开考虑 $h$ 不同的限制。每个的位置的值在包含它的、 $h$ 最小的限制那里确定。

对于某个确定的 $h$ ，如果有两个限制满足 $l_1\le l_2\le r_2\le r_1$ 的，只保留 $[l_2,r_2]$ 就可以了（注意最后要给答案乘上给 $[l_1,l_2)\cup (r_2,r_1]$ 赋值的方案数）。这样处理以后，限制的区间的左右端点都是单调的。

Sol

考虑对每个点算出能够与它进行贸易活动的点数，也就是到它的路径被那 $m$ 条路径中的某一条完全包含的点数。

对原树进行链分治（重链剖分），这样每条路径最多会经过 $\log n$ 条链。

参考 cz_xuyixuan的blog

Sol

把原问题转化成 $\sum_{i=0}^\infty P(S_i 不存在一个子集能胡)$ 。要算这个玩意则需要对每个 $i$ ，求出大小为 $i$ 且加上初始的牌之后不存在胡子集的子集的数量。

0

在使用 vscode 的 markdown preview enhanced 进行预览的时候，经常会出现这种情况：如果行间公式包含了 \\ ，预览就会显示：ParseError: KaTeX parse error: \cr valid only within a tabular/array environment 。重启 vscode 就能恢复正常。

最近无意中发现，如果把公式用 \begin{aligned} 和 \end{aligned} 包围起来，就不会出现上面的问题。

Sol

0

部署方案合法的条件是：存在一个点$u$，使得所有搜救范围都包含$u$且所有在搜救范围中出现过的点到$u$的距离不超过$L$。此时我们称部署方案可以被点$u$识别。

Sol

如何判断 $p^\alpha \mid \binom{n}{k}$ 是否成立：只需要知道 $\binom{n}{k}$ 中 $p$ 的次数是否大于等于 $\alpha$ 。

设 $f(n)$ 为 $n!$ 中 $p$ 的次数，显然有 $f(n) = \sum_{i=1}^\infty \lfloor \frac{n}{p^i} \rfloor$。而我们要做的就是检查 $f(n)-f(k)-f(n-k)$ 是否成立。

Sol

答案相当于 $T$ 中不被 $S_{l\cdots r}$ 包含的本质不同的子串数量。

求出 $T$ 中被 $S_{l\cdots r}$ 包含了的本质不同的子串数量，用 $T$ 的本质不同的子串数量减去它就是答案。后者容易求，我们考虑怎么求前者。

link to the problem

Sol

设 $s(a,b,c,d) = \sum_{i=a}^b \sum_{j=c}^d [ a_i \mid a_j ] + [ a_j \mid a_i ]$