blob: d9c8604fd1f449137b5e45967b7d9f435be3c68a (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
# AiSD, L0Z8
Dane: $n$, $m$.
Wynik: (Współczynnik przy $x^2$) $\mod m$ wielomianu $\underbrace{(\ldots((x-2)^2 -2)^2\ldots - 2)^2}_{n\text{ razy}}$.
**Obserwacja 1:** Wszystkie obliczenia możemy wykonywać $\mod m$. Nie zwiększa to złożoności obliczeniowej, a ogranicza wartości które musimy utrzymywać.
**Obserwacja 2:** Obliczając współczynniki wielomianu nie musimy obliczać współczynników przy większej potędze $x$ niż $2$.
Niech $w_k(x)$ = $\underbrace{(\ldots((x-2)^2 -2)^2\ldots - 2)^2}_{k\text{ razy}}$, ale bez wyrazów gdzie $x$ występuje w potędze większej niż $2$. Dla jasności przyjmujemy $w_0(x) = x$.
Mamy w takim razie $w_k(x) = a_k + b_kx + c_kx^2$. Ponadto:
\begin{align}
w_{k+1}(x) &= (a_k + b_kx + c_kx^2 - 2)^2 \\
&= \underbrace{(a_k^2 - 4a_k + 4)}_{a_{k+1}} + \underbrace{(2a_kb_k - 4b_k)}_{b_{k+1}}x + \underbrace{(2a_kc_k + b_k^2 - 4c_k)}_{c_{k+1}}x^2
\end{align}
Dostajemy zatem układ rekurencyjny:
\begin{cases}
a_0=c_0=0 \\
b_0=1 \\
a_{k+1} = a_k^2 - 4a_k + 4 = (a_k - 2)^2 \\
b_{k+1} = 2a_kb_k - 4b_k \\
c_{k+1} = 2a_kc_k + b_k^2 - 4c_k \\
\end{cases}
**Obserwacja 3:** $a_k = 4$ dla $k \ge 1$. Faktycznie, policzmy $a_1 = (a_0 - 2)^2 = 4$. Ale $a_2 = (4 - 2)^2 = 4$. Zatem ciąg ten jest stale równy $4$ od $k = 1$.
**Obserwacja 4:** $b_k = -(4^k)$ dla $k \ge 1$. Korzystając z zależności rekurencyjnej dla $k \ge 1$ mamy $b_{k+1} = 2b_k(a_k - 2) = 4b_k$, ale $b_1 = -4$, zatem $b_k = -(4^k)$.
Korzystając z obserwacji 3. i 4. upraszczamy zależność rekurencyjną na $c_{k+1}$ dla $k\ge 1$:
\begin{align}
c_{k+1} = 8c_k + 4^{2k} - 4c_k = 4c_k + 4^{2k}
\end{align}
Stąd już dostajemy łatwą zależność (dla $k\ge 1$):
$$
\left[\begin{array}{cc}
4 & 1\\
0 & 16
\end{array}\right]
\left[\begin{array}{cc}
c_k\\
4^{2k}
\end{array}\right] =
\left[\begin{array}{cc}
c_{k+1}\\
4^{2(k+1)}
\end{array}\right]
$$
|
