We read every piece of feedback, and take your input very seriously.
To see all available qualifiers, see our documentation.
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
整数 $q$ および素数 $p$ が与えられる。
$Q$ クエリに答えよ。 $n, r$ が与えられるので、 $q$ - 二項係数 $\binom{\mathbf{n}}{\mathbf{k}}_q$ を $\pmod{p}$ で求めよ。
$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)$ の係数に帰着できるのでよい。
制約は二項係数同様にいくつか考えられますが、とりあえず一番よく使うやつ。
The text was updated successfully, but these errors were encountered:
実装していたら、 $\binom{[n/d]}{[r/d]}$ で $[n/d] \geq p$ が出てきて、そういう二項係数が必要になって、ちょっとうっとおしい(できるけど実用上要らないことが多い処理)
(1) 折角 LC に入れるのでもろもろ頑張る (2) $n,r < p$ ということにする (3) $i\leq n \implies q^i\neq 1$ ということにする
#833 の analogue ということで、(2) の気持ちになっています。
Sorry, something went wrong.
これは analogue で自明なので準備の必要なしという close ですか?
身に覚えのない close 、誤クリックだと思います
よさそうです.制約は (2) に 1 票です. 他の候補: (1) でもいいです. (3) は微妙です. 微妙かもしれませんが p=998244353 にしてしまうのも反対はしないです (q の位数が限られてはしまうがいろいろなサイズにはなる)
(2) でいきましょう。 作業者募集で。
No branches or pull requests
問題概要
整数$q$ および素数 $p$ が与えられる。
制約
解法
例えば
制約は二項係数同様にいくつか考えられますが、とりあえず一番よく使うやつ。
The text was updated successfully, but these errors were encountered: