693
правки
Изменения
→Теорема о связи этих понятий
Заметим, что второй множитель в левой части равен в точности <tex>Q(t)</tex>, а степень правой части не превосходит <tex>k-1</tex>. Получили требуемое построение.
'''Замечание.''' Многочлен <tex>P(t)</tex> можно найти по формуле <tex>A(t) \cdot Q(t)</tex> как числитель получившейся дроби. К результату можно применить взятие его по модулю <tex>t^k</tex>. Это действие не испортит многочлен, так как его степень строго меньше <tex>k</tex>. При этом мы сократим число операций при вычислении <tex>P(t)</tex>, поскольку достаточно найти только <tex>k</tex> первых членов результирующего ряда, а для этого можно обойтись только первыми <tex>k</tex> слагаемыми степенных рядов, соответствующих производящим функциям <tex>A(t)</tex> и <tex>Q(t)</tex>.
<!-------Для того чтобы сократить число операций, все действия могут быть выполнены по модулю <tex>t^k</tex>.-------->
Итак, <tex>P(t) = A(t) \cdot Q(t) \mathrm{ \ mod \ } t^k</tex>.
<!----Значит, многочлены <tex>Q(t)</tex> и <tex>P(t)</tex> всегда могут быть найдены. Более того, многочлен в знаменателе после нашего построения всегда принимает вид <tex>Q(t)=1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k</tex----->
<tex>\Leftarrow</tex>
