Polynomial Construction - abc 137 f

#math

ヒント

すべて 0 の数列から, 1 ずつ足して 0, 1 の数列 a を構成する.

解法

a = 0 ... 0
から
a' = 0 0 ... 0 1 0 ... 0
と, i 番目のみ 1 にすることを考える.

a に対応する f(x) から, a' に対応する f'(x) を構成する.

f'(x) = f(x) + $1 - (x - i)^{p - 1}$ .

x = i のとき, x - i = 0 で, f'(x) = f(x) + 1.

x $\neq$ i のとき, $(x - i)^{p - 1} \equiv 1$ (mod p) で, f'(x) = f(x).

x - i と素数 p が互いに素であることを示す.
$0 \leq i, x \leq p - 1$ .
ただし, x $\neq$ i.

-(p - 1) $\leq$ x - i $\leq$ p - 1.
ここで, x $\neq$ i より, x - i は p の倍数にならない.

以上より, 与えられる a に対して f(x) が求まったので, 各 x の冪乗の係数を求める.

tle 3000 * 3000 * 11 > 10^8

vector<int> b(p);
rep(i, p) {
  if (a[i] == 0) continue;

  b[0]++;
  // (x-i)^(p-1) = (p-1)Cj x^j (-i)^(p-1-j)
  rep(j, p) {
    (b[j] += mod - COM(p - 1, j) * modpow(-i, p - 1 - j, mod) % mod) %= mod;
  }
}

modpow のところを O(1) で計算できる.
j を後ろから走査して, -i をかけていく.

ソースコード
tle
https://atcoder.jp/contests/abc137/submissions/13663541
ac
https://atcoder.jp/contests/abc137/submissions/13663696

参考
https://www.youtube.com/watch?v=1Z6ofKN03_Y