CodeChef July Challenge 2016: Evaluate the polynomial

https://www.codechef.com/JULY16/problems/POLYEVAL

問題

多項式が与えられるので、x[i] での値を mod 786433 で求めよ。

• 1≦N, Q≦250,000

やったこと

• ネット漁れば出てくるかと思ったが出てこない。
• 行列に落としてみたり、分割統治とか考えたが計算量は落ちない（ちょっと速い行列積を使えばオーダーは落ちるけど…）。
• どことなく一般に高速に解ける類の問題ではない気がする。
• 786433 が怪しい。ちょっと小さいので何かを前計算できる？→分からない。
• 試しに 786433-1 を素因数分解してみたら 3*2¹⁸ だと分かった。
• p-1 が大きな 2 の冪を含むような素数と言えば mod FFT。
• DFT は mod の世界でも考えることができる。複素数体上の DFT の回転子と同じような構造を持つものが剰余体上でも存在するため。
• x = w^r と変換してあげれば DFT の結果がそのまま使える。

$$ f(x)=\mathcal{F}[a][r]=a_0+ a_1 (w^r) + a_2 (w^r)^2 + \cdots + a_{N-1} (w^r)^{N-1} $$

• とりあえず原始根が 1 つ欲しいのでループを回す。10 が原始根らしいのでこれを使おう。
• w=10^(p-1)/N の位数は N なので、w が生成する巡回群ではすべての入力をカバーしきれない。
• $\langle w \rangle$ に含まれない適当な元を 2 つ持ってくれば、$(\mathbb{Z}/p\mathbb{Z})^\times=\langle w \rangle+a \langle w \rangle+b \langle w \rangle $ と分解できるはず。
• 次のように分解できた。$(\mathbb{Z}/p\mathbb{Z})^\times=\langle w \rangle+2 \langle w \rangle+4 \langle w \rangle $
• 分解はできたけど、実際に 2w の入力が来たらどう計算する？
• x=2w^r と表せるので、求める値は次のようになる。

$$ a_0+ a_1 (2w^r) + a_2 (2w^r)^2 + \cdots + a_{N-1} (2w^r)^{N-1} $$

• ちょっと式をいじれば次のような感じになる。

$$ a_0+ 2a_1 w^r + 4a_2 (w^r)^{N-1} + \cdots + 2^{N-1} a_{N-1} (w^r)^{N-1} $$

• これは $[a_0,2a_1,4a_2,\ldots,2^{N-1}a_{N-1}]$ を DFT すれば求まる。
• FFT は typical contest のスライドのやり方が楽。これなら空で書ける。

C: 高速フーリエ変換 - AtCoder Typical Contest 001 | AtCoder

mod FFT 知ってた割に気づくのに時間が掛かった。