問題タブ [binomial-coefficients]

変数 (x1、x2、...) と係数 (c1、c2、...) がある多項式の展開を自動的に計算したいと考えています。私の目標は計算することですp(1)*(c1*x1+c2*x2+...)^n+ ... + p(n)*(c1*x1+c2*x2+...)^n .

お気づきのように、結果の式はF(x1,x2...)*g(c1,c2,...)[F は行行列、g は列行列] のように記述できます。つまり、係数と変数の間に何らかの乗法分離があります。

現在、私は MATLAB シンボリック ツールボックスを使用し、結果のシンボリック展開を手動で調べることによって F と g を構築しています。c=(c1,c2,...)n が大きくて大きすぎる場合、項が多すぎて手動では不可能になるため、これはあまり実現可能ではありません。たとえば(c1*x1+c2*x2+c3)とn=2、私が欲しいのは次のとおりです。

次の質問を見つけました。などを使用して自動的に行う方法があるようです。上記のconv場合の自動化されたソリューション（またはそのような自動化に向けた少なくともいくつかのアイデア）を思いつくことができるx=(x1,x2) and c=(c1,c2,c3) and n=2場合; 高次元の場合に一般化できると思います。

注: F または g の項の順序は、構造化された方法で順序付けられている場合、問題ではありません。

少し前に、FFT とバイナリ分割を使用して大きな整数 (最大 500 万) の階乗を計算するために、大きな整数ライブラリを作成しました。ここで、二項係数 (n! /(k! *(nk)!)) を大きな整数 (n=10000 と k=4000 のようなもの) で計算する必要があり、次の間の除算を実装する関数を実現する必要があります。大きな整数、または大きな整数の逆数ですらあります。

では、この機能を実現するためにどのアルゴリズムを使用できるかお尋ねします。

big int を表す構造体の下に投稿します。

"arg" は big int の多項式表現、"size" は桁数、"nsize" は arg の長さです。

下手な英語で申し訳ありません。ご清聴ありがとうございました。

Pythonで二項確率を計算したい。私は式を適用しようとしました：

私が得る確率のいくつかは無限です。p=inf の値をいくつかチェックしました。そのうちの 1 つは、n=450,000 で k=17 です。この値は、float によって処理される最大値である 1e302 より大きくなければなりません。

私はそれから使用しようとしましたsum(np.random.binomial(n,p,numberOfTrials)==valueOfInterest)/numberOfTrials

これは numberOfTrials サンプルを描画し、値 valueOfInterest が描画される平均回数を計算します。

これは無限の値を上げません。しかし、これは続行する有効な方法ですか？そして、確率を計算するのに、なぜこの方法は無限の値を上げないのでしょうか?

二項係数を までの整数として計算したいと思いnumberLeaves=100, K=10ます。これは、約 128 ビットの整数に格納できるはずです。

boost::multiprecision::cpp_intしたがって、結果を保存するために使用し、boost::math::binomial_coefficient<boost::multiprecision::cpp_int>それを計算するために使用したいと思います。

残念ながら、二項係数は整数ですがboost::math::binomial_coefficient、戻り値が浮動小数点型でなければならないため、上記のコードは無効です。

...テンプレートの引数は float や double などの実数値型でなければならず、整数型ではありません。簡単にオーバーフローしてしまいます!

前述のように、私の場合、二項係数計算の結果が約 128 ビット以内に収まることを期待しています。これを整数にしたいと考えています。

boost::multiprecision::cpp_dec_floatしたがって、テンプレート引数として に渡し、(丸めによって) 浮動小数点の戻り値から最も近い整数に変換することを検討しboost::math::binomial_coefficientました。

残念ながら、 a から a に変換する方法が見つかりませboost::multiprecision::cpp_dec_floatんboost::multiprecision::cpp_int。非可逆変換の実行は、ライブラリによって厳密に禁止されているようです。boost::multiprecision

現在、二項係数を計算し、値を整数として返す独自の関数を単純に作成中です。

boost::math::binomial_coefficient二項係数を計算して として返すために使用できる方法が文字通り存在しないとは信じがたいboost::multiprecision::cpp_intです。

boost::math::binomial_coefficient二項係数を計算し、それを として返すために使用することは可能boost::multiprecision::cpp_intですか?

次の式の C++ プログラムを作成しようとしています。

関数の一部を選択しました。

k の出力は空白で、choose() の出力は 000000000000000000000 です

どんな助けでも大歓迎です

等間隔の二項係数モジュロMの合計を見つける方法は?
すなわち。( ⁿ C _a + ⁿ C _{a + r} + ⁿ C _{a + 2r} + ⁿ C _{a + 3r} + ... + ⁿ C _{a + kr} ) % M = ?
与えられた: 0 <= a < r, a + kr <= n < a + (k+1)r, n < 10 ⁵ , r < 100

私の最初の試みは：

しかし、これは効率的ではありません。したがって、ここ とこの論文を読んだ後、上記の
合計が^次 と同等であること^がわかりました。および ω = e ^i2π/rは原始的な 1 の r^乗根です。 Order(r) でこの合計を見つけるコードは何ですか?

編集: n は 10 ⁵まで、r は 100 までです。

元の問題のソース: https://www.codechef.com/APRIL14/problems/ANUCBC
コンテストの問題の編集者: https://discuss.codechef.com/t/anucbc-editorial/5113
この投稿を 6 年間再訪した後後で、元の問題ステートメントを自分のバージョンにどのように変換したか思い出せませんが、正しいソリューション アプローチを見たい人のために、元のソリューションへのリンクを共有しました。

二項係数 mod a 素数を計算する必要があるハッカーランクのコーディングの課題を解決しようとしています。

この回答の最初の 3 つの入力セットで機能するコードを使用していますが、4 番目で失敗し始めます。デバッガーでステップスルーしたところ、次の場合に問題が発生することがわかりました。

n % p == 0 または k % p == 0 の特定のケースを処理するために、現在のソリューションを変更する方法を知る必要があるだけです。スタック交換で見つけた回答は、この特定のケースに対処していないようです。これが私のコードです：

制約:
4 <= N <= 10^9
1 <= K <= N