Logo

菜单

狼群狼某人
发布于 2025-07-16 / 7 阅读
0
0

7.16 神秘课程

P3773 [CTSC2017] 吉夫特 - 洛谷

昨天的残存内容，一道非常优雅且神奇的卢卡斯定理的应用。

它告诉了我们，卢卡斯定理除了屎以外，还有一个和 OI 关联性很高的用法，即将组合数转化为和 p 进制相关的内容：

\begin{aligned} \dbinom{n}{m} \bmod p &= \dbinom{n/p}{m/p} \times \dbinom{n \bmod p}{m \bmod p} \bmod p \\ &= \dbinom{n/p^2}{m/p^2} \times \dbinom{n/p \bmod p}{m/p \bmod p} \times \dbinom{n \bmod p}{m \bmod p} \bmod p \\ &= \cdots \\ &= 1 \times \cdots \times \dbinom{n/p \bmod p}{m/p \bmod p} \times \dbinom{n \bmod p}{m \bmod p} \bmod p \\ \end{aligned}

在上述推导中，可以发现其中每一项都带上了 \bmod p，即将每一项都限制在了 p 以内，即转化到了 p 进制。

在本题中，p=2，所以：

\begin{aligned} \dbinom{n}{m} \bmod p &= \dbinom{(n \gg k) \& 1}{(m \gg k) \& 1} \times \cdots \times \dbinom{(n \gg 1) \& 1}{(m \gg 1) \& 1} \times \dbinom{n \& 1}{m \&1} \bmod 2 \end{aligned}

通过卢卡斯定理进行推导可以发现，问题转化为了遍历每个二进制位，我们又考虑：\binom{1}{1}=1，\binom{1}{0}=1，\binom{1}{1}=1，\binom{0}{1}=0。

1 怎么乘不变，影响答案的只有 0，所以问题转化为遍历二进制位，看看是否存在 n 的某一位是 0，而 m 的那位是 1 的情况，如果有则说明不贡献答案。

DP 即可。

OI 应该删除数论。

P3390 【模板】矩阵快速幂 - 洛谷

对于两个矩阵 A，B，如果其大小分别为 a \times b 和 b \times c，可以计算出一个新矩阵 C，其大小为 a \times c，其计算公式为：

C_{i,j}= \sum_{k=1}^{b} A_{i,k} \times B_{k,j}

矩阵想要进行乘法运算，必须满足前者的列数等于后者的行数，且 A \times B 在定义上不等于 B \times A。

在本题中，需要进行快速幂运算，直接通过重载矩阵结构体的乘法运算符，再搭配普通的快速幂即可解决。

P1962 斐波那契数列 - 洛谷

如果你不会矩阵加速推斐波那契数列，那么你只能度过一个相对失败的人生。

我们考虑对于 F_n=F_{n-1}+F_{n-2}，所以应该有一个矩阵 base 使得

\begin{bmatrix} F_{n-1} & F_{n-2} \end{bmatrix} \times base = \begin{bmatrix} F_{n} & F_{n-1} \end{bmatrix}

因为 F_n=1 \times F_{n-1} + 1 \times F_{n-2}，F_{n-1} = 1 \times F_{n-1} + 0 \times F_{n-2}，所以 base 的第一、二列应该分别是 \begin{bmatrix} 1 \\ 1 \end{bmatrix}，\begin{bmatrix} 1 \\ 0 \end{bmatrix}，得到 base 为 \begin{bmatrix} 1 & 1 \\ 1 & 0\end{bmatrix}。

从 F_2=1 开始，每一次的 F_n 都可以通过乘一次 base 得到 F_{n+1}，所以只需要定义 F_2=F_1=1，对其进行 n-2 次矩阵快速幂即可得到答案。

根号分治——平衡规划思想的应用
整体二分

评论