当前位置：首页 > news >正文

7.29 数论，计数

news 2026/7/29 22:36:54

Color Ball

给定 $n$ 个筒，第 $i$ 个筒装有颜色为 $i$ 的球 $a_i$ 个，重新排布这些球，使得每个筒中的球个数不变，且没有筒装有颜色与其编号相同的球，求排布方案数。不考虑同色球的差异，但是区分筒中求从下到上的排列顺序。

$1 \le \sum a_i, n \le 2000$

考虑直接容斥，设前 $i$ 个筒，有 $j$ 个球被放在不合法的位置，用 dp 算容斥系数与方案数的乘积即可。

[NordicOI 2017] Yule Lads

有 $n$ 个人与 $n$ 盏灯，初始状态都为开，人的编号分别为 $1 \sim n$，他们其中的 $k$ 个人参与了按灯事件。

我们定义一次按灯事件为一个编号为 $i$ 的人调整了所有编号为 $i$ 的倍数的灯的开关状态（关变开，开变关）。

你知道 $k$ 是多少吗？

$1 \le n \le 10^{13}$。

设按灯者集合为 $S$，则我们有：$\varepsilon(i) = [i = 1] \equiv \displaystyle\sum _{j \in S, j|i} 1 \pmod 2$。设 $g_S(n) = [n \in S]$，则 $g_S * 1 \equiv \varepsilon \pmod {2}$。

两边同时卷上 $\mu$，由莫比乌斯反演可以得到 $g_S \equiv \mu \pmod {2} $，所以说只需要求 $\mu(i) \neq 0$ 的个数即可。考虑 $\mu$ 的含义，容易转化为 $1 \sim n$ 无平方因子的数的个数。枚举平方因子，套路地容斥计算：

\[\sum _{d=1}^{\lfloor \sqrt n\rfloor}\mu(d) \left\lfloor\dfrac{n}{d^2}\right\rfloor \]

[QOJ14414] Nice Subsequences

难度：提高

给定长为 $n$ 的序列 $a$，求其最长的子序列满足相邻项不互质，并求长度最大时，子序列的个数。

$1 \le n \le 2 \times 10^5, 1 \le a_i \le 10^6$

容易发现对于从 $i$ 转移的时候，若 $j < k$，且 $\gcd(a_i, a_j, a_k) = p$，则直接先由 $i$ 转移到 $j$ 一定更有。考虑枚举 $a_i$ 的每一个本质不同的质因子 $p$，连接边 $i \to j$，其中 $j$ 是满足 $j > i \land p\operatorname{|}a_j$ 的最小值。

然后跑 DAG 上 dp 就行了。

[QOJ18107] Parentheses

对于括号串的编辑如下：

选择区间 $[L, R]$，反转后逐个翻转每个括号，例如左括号翻成右括号。

一个括号串的权值为最少编辑次数，使得括号串合法。对 $0 \le i \le n$，求长度为 $n$ 且值为 $i$ 的不同括号串总数 $A_i$，计算 $\displaystyle\sum _{i=0}^n (i+1)A_i$ 的值。

$n \le 10^6$。

还是用一个经典的转换，设 ( 为 $1$，) 为 $-1$，求前缀和 $s$，要求 $s_i \ge 0$，且 $s_n=0$。

容易发现这个套路我们见过，但好像又不太一样，考虑这个编辑操作实际上是什么：

对于 $i < l$，没有影响，对于 $i>r$，都有 $s_i \gets s_i +2(s_{l-1}-s_r)$。
内部 $l \le i \le r$：反转+翻转操作等价于 $s_{l+r-i} \gets s_{l-1}-(s_r-s_{l-1})+(s_{i-1}-s_{l-1}) = (s_{l-1}-s_r)+s_{i-1}$。

相当于将 $[l, r-1]$ 反转后，对于 $i \in [l, r-1]$ 的每个数加上 $(s_{l-1}-s_r)$。

把问题画在图上（描点 $(i, s_i)$），令 $n$ 为偶数，容易发现：

操作为反转该段折线，并对齐到折线起点上。
第一种情况，无位置 $s_i < 0$，且 $s_n=0$ 则值为 $0$。
第二种情况，无位置 $s_i < 0$，且 $s_n>0$，则值为 $1$。

设 $s_n=d$，构造方法是只需要找到高度差为 $\dfrac{d}{2}$ 的 $s_{l-1}, s_r$ 即可。令 $r$ 为 $n$，一定能找到第一个 $s_{l-1}=\dfrac{2}{n}$，则其中间的 $i \in [l,r]$ 都满足 $s_i > \dfrac{d}{2}$，所以反转后对齐，这一部分不会 $<0$。
第三种情况，存在位置 $s_i < 0$，怎么办，我们先找到最小的位置，记为 $s_x$，则：

由于 $s_x$ 已经是最小的，且 $s_0 = 0$，找到 $s_{l-1}-s_r=-s_x$ 是一定能够找到的。所以可以通过一次操作使 $s_x' \ge -s_x$，然后其余 $< 0$ 的位置就可以通过 $-s_x \ge -s_i$ 的原理，达到 $\ge 0$ 的效果，可以一步操作，使这些位置均 $\ge 0$，且 $s_n=0$.所以最多操作两次。而操作一次当且仅当 $s_x$ 是所有 $<0$ 中最靠右的，容易发现必然为 $s_n$。