2020-09-02

FFTを学ぶときに見かけるNTTって一体なんなの

前書き

regiです。この記事ではあくまでもNTT(数論変換)のみを取り上げるため、FFT(高速フーリエ変換)について全く知らない方でもある程度知っている方でも関係なく、ただNTTって何なのかだけざっくり押さえておきたい！と思っている方を対象としています。しかし、備忘録という意味合いが強いため、今のところでは細かい事や実装例等は取り上げていないのでご了承ください。その代わり、私が参考にさせて頂いた他の方のFFTやNTTに関する記事を適宜紹介したいと思っています。また、この記事内で誤った情報、誤字、誤植等を見かけた場合、直ちに訂正するのでTwitterで教えて欲しいです...お願いします🙏(TwitterID -> @Re_code_A)

FFTで用いられる数について

正確に言うと、FFTを行う際に行われるDFT(離散フーリエ変換)で用いられる数であり、 $\zeta _{N}$ という複素数が用いられています。 $N$ は必ず $2$ のべき乗とします。これは $1$ の原始 $N$ 乗根と呼ばれる $N$ 乗して初めて $1$ になる数のことであり、 $\cos \dfrac{2\pi }{N}+i\sin \dfrac{2\pi }{N}$ などが原始 $N$ 乗根に該当します。そもそもなぜこのような数がFFTで用いられているかというと、 $\zeta _{N}$ は重要な性質を持っているからであり、それは以下のようなものです。

$\zeta _{N}^{i}=\zeta _{N}^{i+N}$
$\sum ^{N-1}_{i=0}\zeta _{N}^{i\left( j-k\right)}=$ $\begin{cases}N\ \ \bf if \ \it \ j\equiv k \bf \ \ \ mod \it \ N\\0 \ \ \ \bf otherwise\end{cases}$

なぜこの性質は重要かというと、単純に、FFTはこのような性質を持つ数を用いることで行うことが可能になるからです。

複素数の概要及び上記の性質の証明等はこちらの記事が大変参考になりました。

https://qiita.com/ageprocpp/items/0d63d4ed80de4a35fe79

NTTとは

先ほど、FFTには $\zeta _{N}$ という複素数が用いられると言いましたが、この場合小数が出てくるために誤差を考慮する必要があるため、その点では複素数を扱うのは不便です。また、上記の性質を持つ数を用いることでFFTを行うことが可能になるとも言いましたが、これを言い換えると、この性質さえ持つ数であればFFTで用いる数として代用できるということで、つまり、上記の性質を満たした整数があるとすると、それを用いれば誤差に怯えることなくFFTを行うことができるということです。このような整数は特別な素数を法とすることで設けることができます。NTTとは、その特別な素数を法とした上で上記の性質を満たした整数を用いてFFTを行う手法のことです。

どのような素数や整数を用いるのか具体的に紹介すると、まず特別な素数とはある正の整数 $u,e$ を用いて $u×2^e+1$ と表すことのできる素数(以下 $pとする$ )であり、 $p$ を法とすると、 $2^e$ 乗して初めて $1$ と合同になる整数 $a$ を設けることができます。この $a$ は法 $p$ の下で以下のような性質を持っています。(ただし、 $N\leq 2^{e}$ であることが必要です。)

$a^{i}\equiv a^{i+N}$
$\sum ^{N-1}_{i=0}a^{i\left( j-k\right)}\equiv$ $\begin{cases}N\ \ \bf if \ \it \ j\equiv k \bf \ \ \ mod \it \ N\\0 \ \ \ \bf otherwise\end{cases}$

確かに $a$ はFFTを行うために必要な性質を持っていることが分かります。

証明等はこちらのパワーポイントが大変参考になりました。

https://hcpc-hokudai.github.io/archive/math_fft_002.pdf

少し余談ですが、プログラミングコンテスト等で見かける $998244353$ という謎の素数は、 $119×2^{23}+1$ と、 $e$ の十分大きい $u×2^e+1$ という形にすることができます。そのため、法 $998244353$ の下で解く問題とNTTを用いたFFTは相性が良いです。ちなみにこの場合は $3$ などが $a$ に該当します。

まとめ

FFTを行うためには $\zeta _{N}$ という重要な性質を満たす複素数が用いられているが、小数が出てきてしまうため誤差が怖い。それを解決する手法である、ある特別な素数を法とすることで、整数を用いてFFTを行えるようにする手法がNTTである。

後書き

私自身がNTTについて初めて学んだとき、このようなところでも整数論が活躍していることにかなり驚きました。その他、NTTに関して参考にさせて頂いた記事を紹介します。

http://kirika-comp.hatenablog.com/entry/2018/03/12/210446

私自身もまだまだ勉強している途中なので、進み次第、いろいろ追記していく予定です。

2020-06-22

ABC171-F : Strivoreの解き方が少し想定解法と違ったので書き残しておく

競技プログラミング AtCoder ABC 別解

想定解法と少し考え方が違ったので、私の解法を書いとこうかと思います。

注意：備忘録のようなものなので、少し解説としては雑です。ご了承ください。

まず、「好きな英小文字 $1$ 文字を好きな位置に挿入する」という操作を文字列 $S$ にちょうど $K$ 回繰り返してできる文字列は何通りあるでしょう？という問題は、 $\left( K+\left| S\right| \right)$ 文字の英小文字から成る文字列はいくつあるでしょう？という問題に帰着させることができる。

ここで、 $S$ の頭 $i$ 文字を部分文字列(連続とは限らない)として含むかつ、頭 $\left( i+1\right)$ 文字は部分文字列として含まない $\left( K+\left| S\right| \right)$ 文字の英小文字から成る文字列の集合を $A_{i}$ とし、その要素数を $f\left( i\right)$ とする。 $\left( 0\leq i\leq \left| S\right| -1\right)$

また、便宜上 $S$ を部分文字列として含む $\left( K+\left| S\right| \right)$ 文字の英小文字から成る文字列の集合を $A_{\left| S\right| }$ とし、その要素数を $f\left( \left| S\right| \right)$ とすると、式 $\sum ^{\left| S\right|}_{i=0}f\left( i\right) =26^{ K+\left| S\right| }$ が成り立つ。なぜなら、任意のある $\left( K+\left| S\right| \right)$ 文字の英小文字から成る文字列において、 $A_{0},A_{1},\ldots ,A_{\left| S\right|}$ のいずれか1つのみに必ず属すからだ。

出力する解は $f\left( \left| S\right| \right)$ であるが、私は直接求めるのではなく、上記の式を変形し、 $f\left( \left| S\right| \right)=26^{K+\left| S\right|}-\sum ^{\left| S\right|-1}_{i=0}f\left( i\right)$ としてから求めた。 $0\leq i\leq \left| S\right| -1$ において、 $f\left( i\right)$ は次のようなイメージで求めた。(図中のS_kを $S$ の $k$ 文字目とする)

f:id:regichan:20200622022835p:plain 上図のような $\left( K+\left| S\right| \right)$ 文字の英小文字から成る文字列は全て $A_{i}$ に属し、逆に $A_{i}$ に属す文字列は全て上図のような $\left( K+\left| S\right| \right)$ 文字の英小文字から成る文字列となるのは明確である。まず、 $S_{1},S_{2},\ldots ,S_{i}$ の配置パターン数は ${}_{K+\left| S\right|} C_{i}$ である。次に、ある配置パターンにおいてその他の文字を配置するパターン数は $25^{K+\left| S\right|-i}$ である。 $S_{1},S_{2},\ldots ,S_{i}$ の配置パターンが異なる場合、文字列がダブることはないため、上図のような $\left( K+\left| S\right| \right)$ 文字の英小文字から成る文字列の数すなわち $f\left( i\right)$ は、 ${}_{K+\left| S\right|} C_{i}\times 25^{K+\left| S\right|-i}$ となる。下処理を $O\left( K+\left| S\right|\right)$ で行うことで各iにおける $f\left( i\right)$ を定数時間で求めることができるため、全体として $O\left( K+\left| S\right|\right)$ で解くことができる。

2020-06-17

AtCoder水色になりました

水コーダー入水記事色変記事競技プログラミング AtCoder 精進法

regiです。遂にAtCoder水色になることができました。

f:id:regichan:20200615212014p:plain

水になったときのAC数です。

f:id:regichan:20200615212556p:plain

とりあえず冒頭で水色になるまでにAtCoderで使ったことのあるアルゴリズム・データ構造の一部を載せておきます。

bitを用いた全探索
再帰関数を用いた全探索
二分探索
三分探索
幅優先探索(BFS)
深さ優先探索(DFS)
imos法
LISを求めるDP
ダイクストラ法
ワーシャルフロイド法
モジュラ逆数(逆元)
動的計画法(DP)
分割統治法
再帰関数用いた木DP
全方位木DP
クラスカル法(最小全域木を求めるアルゴリズム)
フォード・ファルカーソン法(最大流を求めるアルゴリズム)
セグメント木

この記事の本題では、私の精進方法や精進とコンテストで意識していることを書こうかと思います。(Lorentさんネタ提供ありがとうございます)

精進方法

基本的には、自分が解けそうな難易度の未ACの問題を無作為に選んで、それを解いていきます。その問題を解くとき、私は大体は以下のような流れに沿っています。

f:id:regichan:20200615221549p:plain

「大体放置」のところで「えっ？」となりそうなので補足します。個人的に、自分の実力帯では到底解けるとは考えられないくらいに難易度の高い問題を解説を参考にACするのは比較的モチベーションになりづらいと思っているため、敢えて放置しています。もちろん、自力で解けるか腕試しにその問題に果敢に立ち向かって考えてみるのは良いことですし、それを解説を参考にACすることで得られる知見や達成感も少なくはないですが、考察すらできないということは、一部の奇問を除き、大体の場合はその問題を解く上での要求される知識や基礎が身についていないということだと思っていて、そのような問題を解説を参考にACしようとなると正直気が遠くなります。やはりそういった知識や基礎は適正の問題でつけ、それから難易度の高い問題に挑戦していく方が私自身としてはモチベーションになりやすいかなと感じています。それに、その難易度の高い問題を解けてもおかしくないような実力になれたとき、未ACである適正の問題が減ってしまうため単純にもったいないです。そういうわけで私はこのような精進方法を採用しています。

精進で意識していること

主に3つあります。

1つ目は、AC出した後もその問題について考察することです。具体的には、「この解法は本当に正しいのか」「コードが冗長ではないか」「解説はどのような解法を想定としているか」「他の同言語のACコードと比べて実行時間とメモリはどうか」などを調べたり考えたりします。ここの考察で明らかまずかった点が見つかった場合は反省するようにして、次に活かせるようにしています。また、その問題を解く上で用いた考え方を適用できうる問題が過去に解いたことのある問題にあったかどうかも考えておくと、問題を解く上で開けられる引き出しの数が多くなるので、私はいつもやっています。

2つ目は、問題を初めて見てからACまでにかかった時間を測ることです。毎回時間を測ることで、自分はどういう問題の考察が苦手か、また、どういう実装が苦手かがより見えてくるため、とても役立っています。

3つ目は、精進を「過去最高パフォーマンスを出すための精進」と「負けても最低限確保するパフォーマンスのラインを引き上げる精進」の2種類に分けることです。私は前者を「上限を伸ばす精進」、後者を「下限を伸ばす精進」と言うのが好きなので、この記事内ではそう表現します。まず、上限を伸ばす精進とは、自分の適正難易度より"やや"高い問題を時間をかけて考えてみるという精進です。この精進をすることで、難易度の高い問題にも考え抜き実装しきる力がついていきます。次に、下限を伸ばす精進とは、自分の適正難易度の問題あるいはそれよりやや低い問題をACしていく精進です。この精進をすることで、最低限通すべき問題をしっかり通せるほどの基礎力がついていきます。このように考えることによって、どちらかが疎かになりすぎていないか、今の自分にはどちらを優先してやるべきかなども考えることができるため、とても役立っています。

コンテストで意識していること

とにかく慌てないで問題文と制約を読むことを意識しています。誤読して数十分無駄にするよりも数秒冷静にしっかり読む方が良いです...。また、考察は一度無理そうだと思った解法は一旦捨て、別の解法を考えるように意識しています。無理そうな解法をずっと考えたって大体はどうにもならないですから...。ただ、万策尽きた場合に限り、一旦捨てた解法も再び考えたりします。そして、解けそうな問題が無くなったら、各問題のAC者数を順位表から直ちに見るようにしています。コンテスト中に難易度の高い問題に時間をかけるよりかは、みんなが通してる問題に時間をかけた方が良いですし、稀に点数と難易度が合わないこともあるからです。

最後に

ここまで読んでいただきありがとうございます。できる限り私自身の考えが伝わるように努めたつもりですが、もし分かりにくい部分があったらごめんなさい＞＜