nCr(組み合わせ/コンビネーション)の高速な計算をしたい!
今、諸事情でnCrの高速な計算方法を探索しています。
以下のコードは、ありきたりなnCrの求め方ですが、もしもっと高速に計算することができるアルゴリズム/コードがあれば教えてほしいです。(キャッシュ併用するものでも可)
cpp
1long nCr(int n, int r) { 2 long ans = 1; 3 for (int i = n; i > n - r; --i) { 4 ans = ans*i; 5 } 6 for (int i = 1 ; i < r + 1; ++i) { 7 ans = ans / i; 8 } 9 return ans; 10}
回答5件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。