これの解説を書きます．
問題概要
素数 \(p\) と長さ \(p\) のバイナリ列 \(a_0, \dots, a_{p-1}\) が与えられる． \(f(x) = \sum_{i=0}^{p-1} b_i\cdot x^i\) であって，\(f(j) = a_j\) となるようなものの係数 \(b_i\) を求めてね．
ぼんやり思うこと
まず，構築問題のおきまりとして，サンプルは可能か不可能かの判定のみに使うというのがあります． うまくないやり方で構築されていがちなので，考察の邪魔になりがちだからです（だめ方針として参考にするのはアリかも）．
特に，今回のように常に構築可能なことが保証されている場合は見る価値が実質ないかなと思って取りかかりがちです（えびちゃんは）．
// 今回は実は一意なので，サンプルを見てもいいです．
考察
今回，\(p-1\) 次式で，\(p\) 個の点が定められているので，バイナリ列に限らず，\(0 \le a_i < p\) の場合で構築可能です．一般に，\(k\) 個の点を通る \(k -1\) 次式が作れるためです．（\(3\) 点を通る放物線とかを必要に応じて想像する．）
ところで，入力の通り数は \(p^p\) 通りあり，一方で出力も \(p^p\) 通りあることがわかります． 各入力に対してある出力を構築できて，入力と出力の通り数が同じなので，一意に定まるなぁみたいな気持ちになります．
や，実際には，\(k\) 個の点を通る \(k -1\) 次式は一意に構築可能であるというのを覚えておくべきっぽい．
ぺたり
えーい！
これの冒頭に書いてある \(l_j(x)\) なる関数は，\(l_j(x_j) = 1\) であり，しかも \(x_i\neq x_j\) なる \(x_i\) に対して \(l_j(x_i) = 0\) となってくれる便利なものです．
なので，\(x_j = j\) として，適当に構築しちゃえばよいです．
つまり，\(f(x) = 0\) で初期化しておき，各 \(j\) について \(a_j = 1\) なら \(f(x) \gets f(x) + l_j(x)\) とすればよいですね．
ぺたぺた
ところで，Fermat の小定理を知っていますか？ 素数 \(p\) と \(0 < a < p\) に対して以下が成り立ちます．
\[a^{p-1} \equiv 1 \pmod{p}.\]
また，当然 \(0^{p-1} = 0\) です． これらより，以下の関数が mod \(p\) で \(l_j(x)\) と一致することがわかります．
\[l_j(x) = 1 - (x-j)^{p-1}.\]
\((x-j)^{p-1}\) の各係数を二項係数かなんかをつかって適当に求めてあげて（あるいは適当に多項式の乗算をがんばって），\(a_j\) を見ながら足したり足さなかったりしていくとよさそうです．
しくしく
本番では，えびちゃんはリンク先にある \(l_j(x)\) をそのまま求めようとして，適当に多項式除算を実装しようとしたら無限にバグらせてつらかったです．
