差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:intrepidsword:zhongzihao:rs [2020/05/24 22:11]
admin init
+++ 2020-2021:teams:intrepidsword:zhongzihao:rs [2020/05/25 12:13] (当前版本)
admin
@@ 行 1: / 行 1: @@
-===== Reeds-Sloane 算法学习笔记 =====
+====== Reeds-Sloane 算法 ======
+===== 算法介绍 =====
 Reeds-Sloane 算法是 BM 算法的拓展，可以处理模任意正整数的递推式。
@@ 行 5: / 行 7: @@
 设环 $\mathbb{Z}/m\mathbb{Z}$ 上有一数列 $s_{0},s_{1},\cdots,s_{n-1}$，我们想要找到一个尽可能短的数列 $a_{0}=1,a_{1},\cdots,a_{l}$，使得 $\sum_{i=0}^{l}a_{i}s_{j-i}=0$ 对 $j=l,l+1,\cdots,n-1$ 成立。
-不妨用多项式的语言来简单地定义一下递推式的长度：设 $a(x)=\sum_{i=0}^{l}a_{i}x^{i}$，$S(x)=\sum_{i=0}^{n-1}s_{i}x^{i}$，$a(x)S(x)\equiv b(x)\pmod{x^{n}}$，定义二元组 $A=(a(x),b(x))$，则定义二元组 $A$ 的长度 $L(A)=\max\{\deg(a(x)),\deg(b(x))+1\}$。当 $\deg(a(x))\le\deg(b(x))$ 时可能有些不好理解，这里可以当做是 $a$ 后面补充了一些 $0$，以跳过开始若干不满足递推式的项。
+不妨用多项式的语言来简单地定义一下递推式的长度：设 $a(x)=\sum_{i=0}^{l}a_{i}x^{i}$，$S(x)=\sum_{i=0}^{n-1}s_{i}x^{i}$，$a(x)S(x)\equiv b(x)\pmod{x^{n}}$，定义二元组 $A=(a(x),b(x))$，其长度 $L(A)=\max\{\deg(a(x)),\deg(b(x))+1\}$。当 $\deg(a(x))\le\deg(b(x))$ 时可能有些不好理解，这里可以当做是 $a$ 后面补充了一些 $0$，以跳过开始若干不满足递推式的项。
 ==== 中国剩余定理 ====
-设 $m=\prod p_{i}^{e^{i}}$，假设我们能够对每个 $p_{i}^{e_{i}}$ 求出递推式，那么对递推式的每一项做 crt 即可得到模 $m$ 意义下的一个递推式，且显然长度不变。当然也容易证明不存在比这长度更短的递推式，否则对于递推式最长的那个质因子会产生矛盾。因此我们将问题归约到了模质数的幂。下面设模数为 $p^{e}$。
+设 $m=\prod p_{i}^{e_{i}}$，假设我们能够对每个 $p_{i}^{e_{i}}$ 求出递推式，那么对递推式的每一项做 crt 即可得到模 $m$ 意义下的一个递推式，且显然长度不变。当然也容易证明不存在比这长度更短的递推式，否则对于递推式最长的那个质因子会产生矛盾。因此我们将问题归约到了模质数的幂。下面设模数为 $p^{e}$。
 ==== 算法介绍 ====
@@ 行 55: / 行 57: @@
 <HTML><ul></HTML>
-<HTML><li></HTML>若 $u_{\eta k}=e$，那么令 $A_{\eta}^{(k+1)}=A_{\eta}^{(k)}$。显然 $\mathscr{E}_{\eta}^{(k+1)}$ 中的最短的元素要大于等于 $\mathscr{E}_{\eta}^{(k)}$ 中最短的元素，而我们又归纳假设 $A_{\eta}^{(k)}$ 是最短的元素，因此 $A_{\eta}^{(k+1)}$ 也是最短的元素。<HTML></li></HTML>
+<HTML><li style="color:black"></HTML>若 $u_{\eta k}=e$，那么令 $A_{\eta}^{(k+1)}=A_{\eta}^{(k)}$。显然 $\mathscr{E}_{\eta}^{(k+1)}$ 中的最短的元素要大于等于 $\mathscr{E}_{\eta}^{(k)}$ 中最短的元素，而我们又归纳假设 $A_{\eta}^{(k)}$ 是最短的元素，因此 $A_{\eta}^{(k+1)}$ 也是最短的元素。<HTML></li></HTML>
-<HTML><li></HTML>若 $u_{\eta k}<e$，令 $g=e-1-u_{\eta k}$，并且记 $f(\eta,k)=g$，下面再分两种情况讨论：
+<HTML><li style="color:black"></HTML>若 $u_{\eta k}<e$，令 $g=e-1-u_{\eta k}$，并且记 $f(\eta,k)=g$，下面再分两种情况讨论：
 <HTML><ul></HTML>
-<HTML><li></HTML><HTML><p></HTML>若 $L(A_{g}^{(k)})=0$，那么令 $A_{\eta}^{(k+1)}=A_{\eta}^{(k)}+(0,\theta_{\eta k}p^{u_{\eta k}}x^{k})$。显然有 $L(A_{\eta}^{(k+1)})=k+1$。<HTML></p></HTML>
+<HTML><li style="color:black"></HTML><HTML><p></HTML>若 $L(A_{g}^{(k)})=0$，那么令 $A_{\eta}^{(k+1)}=A_{\eta}^{(k)}+(0,\theta_{\eta k}p^{u_{\eta k}}x^{k})$。显然有 $L(A_{\eta}^{(k+1)})=k+1$。<HTML></p></HTML>
 <HTML><p></HTML>由于 $L(A_{g}^{(k)})=0$，每个 $s_{0},\cdots,s_{k-1}$ 都是 $p^{e-g}$ 的倍数，不妨设 $s_{i}=p^{e-g}s'_{i}(0\le i\le k-1)$，又由 $\theta_{gk}$ 和 $u_{gk}$ 的定义有 $s_{k}p^{g}=\theta_{gk}p^{u_{gk}}$，从而有 $(p^{e-g}(s'_{0}+s'_{1}x+\cdots+s'_{k-1}x^{k-1})+\theta_{gk}p^{u_{gk}-g}x^{k})(p^{\eta}+\cdots)\equiv b_{\eta}^{(k)}(x)+\theta_{\eta k}p^{u_{\eta k}}x^{k}\pmod{x^{k+1}}$。<HTML></p></HTML>
 <HTML><p></HTML>另外注意到 $b_{\eta}^{(k)}$ 是在 $\pmod{x^{k}}$ 意义下的，从而度数小于等于 $k-1$。比较 $x^{k}$ 的系数，有 $\alpha p^{e-g}+\theta_{gk}p^{u_{gk}+\eta-g}=\theta_{\eta k}p^{u_{\eta k}}$。又由于 $e-g=u_{\eta k}+1$，而 $\theta_{gk},\theta_{\eta k}\in R^{*}$，因此 $u_{gk}+\eta-g\le u_{\eta k}$，$u_{gk}+\eta\le e-1$。另外有 $A_{\eta}^{(k+1)}\in\mathscr{E}_{\eta}^{(k+1)}$，$A_{g}^{(k)}\in\mathscr{B}_{u_{gk}}^{(k)}$，从而 $L(A_{\eta}^{(k+1)})+L(A_{g}^{(k)})\ge k+1$，因此 $L(A_{\eta}^{(k+1)})$ 取到了最小值。<HTML></p></HTML><HTML></li></HTML>
-<HTML><li></HTML><HTML><p></HTML>若 $L(A_{g}^{(k)})>0$，那么一定存在唯一的一个 $r$ 使得 $L(A_{g}^{(r)})<L(A_{g}^{(r+1)})=L(A_{g}^{(k)})$。由归纳假设可知 $g+u_{hr}<e$，又 $g=e-1-u_{\eta k}$，从而 $u_{hr}\le u_{\eta k}$。<HTML></p></HTML>
+<HTML><li style="color:black"></HTML><HTML><p></HTML>若 $L(A_{g}^{(k)})>0$，那么一定存在唯一的一个 $r$ 使得 $L(A_{g}^{(r)})<L(A_{g}^{(r+1)})=L(A_{g}^{(k)})$。由归纳假设可知 $g+u_{hr}<e$，又 $g=e-1-u_{\eta k}$，从而 $u_{hr}\le u_{\eta k}$。<HTML></p></HTML>
 <HTML><p></HTML>我们令 $a_{\eta}^{(k+1)}=a_{\eta}^{(k)}(x)-\theta_{\eta k}\theta_{hr}^{-1}p^{u_{\eta k}-u_{hr}}x^{k-r}a_{h}^{(r)}(x)$，$b_{\eta}^{(k+1)}=b_{\eta}^{(k)}(x)-\theta_{\eta k}\theta_{hr}^{-1}p^{u_{\eta k}-u_{hr}}x^{k-r}b_{h}^{(r)}(x)$。<HTML></p></HTML>
 <HTML><p></HTML>我们来验证 $a_{\eta}^{(k+1)}S(x)\equiv b_{\eta}^{(k+1)}(x)\pmod{x^{k+1}}$。<HTML></p></HTML>
@@ 行 91: / 行 93: @@
 两个实现时的数值分析与 BM 算法类似，从而有：对于一个由 $k$ 阶矩阵转移而来的数列，至多需要 $2k$ 项即可由 RS 算法计算出递推式。
+===== 例题 =====
+暂时没有见到如此丧心病狂的出题人，不过应用场景与 BM 算法类似，可参考 BM 算法的例题。
+===== 参考文献 =====
+[1] Reeds J A, Sloane N J A. Shift register synthesis (modulo m)[J]. SIAM Journal on Computing, 1985, 14(3): 505-513.

CVBB ACM Team

用户工具

站点工具

差别

页面工具