[Problem proposal] $q$ - Binomial Coefficient (Prime Mod)

[maspypy]

問題概要

整数 $q$ および素数 $p$ が与えられる。

$Q$ クエリに答えよ。 $n, r$ が与えられるので、 $q$ - 二項係数 $\binom{\mathbf{n}}{\mathbf{k}}_q$ を $\pmod{p}$ で求めよ。

制約

• $1\leq Q\leq 10^6$
• $1\leq p\leq 10^9$、素数
• $0\leq q < p$
• $0\leq n, r \leq 10^7$

解法

$q^d = 1\pmod{p}$ となる最小の $d$ をとる。 $10^7$ までになければ $d = \infty$。 $n, r < d$ のときは、階乗前計算でできる。

$n,r > d$ のときは、二項係数と小さい $q$ - 二項係数の積として表せる。 例えば $\displaystyle \prod_{i=0}^{n-1} (1-q^ix)$ の係数を求める問題と思うと、連続する $d$ 個の積が $1-x^d$ であることより $\displaystyle(1-x^d)^a \prod_{i=0}^{b-1} (1-q^ix)$ の係数に帰着できるのでよい。

---

制約は二項係数同様にいくつか考えられますが、とりあえず一番よく使うやつ。

[maspypy]

実装していたら、 $\binom{[n/d]}{[r/d]}$ で $[n/d] \geq p$ が出てきて、そういう二項係数が必要になって、ちょっとうっとおしい（できるけど実用上要らないことが多い処理）

(1) 折角 LC に入れるのでもろもろ頑張る (2) $n,r < p$ ということにする (3) $i\leq n \implies q^i\neq 1$ ということにする

https://github.com/yosupo06/library-checker-problems/issues/833 の analogue ということで、(2) の気持ちになっています。

[noshi91]

これは analogue で自明なので準備の必要なしという close ですか？

[maspypy]

身に覚えのない close 、誤クリックだと思います

[hos-lyric]

よさそうです．制約は (2) に 1 票です． 他の候補： (1) でもいいです． (3) は微妙です． 微妙かもしれませんが p=998244353 にしてしまうのも反対はしないです (q の位数が限られてはしまうがいろいろなサイズにはなる)

[maspypy]

(2) でいきましょう。 作業者募集で。