2020-2021:teams:intrepidsword:zhongzihao:rs

差别

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

到此差别页面的链接

--- 2020-2021:teams:intrepidsword:zhongzihao:rs [2020/05/24 22:18]
admin fix color
+++ 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}$。
 ==== 算法介绍 ====
@@ 行 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.

2020-2021/teams/intrepidsword/zhongzihao/rs.1590329917.txt.gz · 最后更改: 2020/05/24 22:18 由 admin