割った余りを出力させる問題が出題されることがあります。素数を使用することなどが多いです。単純に計算すると、\(\frac{n!}{k!(n-k)!}\)を計算してから割ることになりますが、値が非常に大きくなってしまいます。32bitや64bitの整数には収まり切らないかもしれません。上手く行ったとしても、1つの二項係数を計算するのに\(O(n)\)だけかかってしまいます。割った余りを定数時間で求められるようになります。サイズ・二項係数を何回計算するのか、などによって最適なアルゴリズムが変わってきますが、ここではよく使われる手法について説明します。した時に、以下のように計算します。整数をオーバーしてしまうかもしれないので注意が必要です。メモ化や動的計画法と呼ばれる方法で、高速に計算することができます。番目の計算結果を、(i+1)番目の計算のときに利用することで、早い計算が可能になるのです。数式では以下のようになります(説明は後述)。割った数の小数点以下を切り捨てた数です。よって以下のようにプログラムを書けば良いです。求めると\(O(n)\)かかります。階乗と逆元の値さえわかっていれば\(O(1)\)で計算できます。