キャッシュを使った階乗計算

# 問題

```math
\begin{align}
&整数nが与えられる。X=n!\mod(10^9+7)を答えよ。\\
&入力:n\quad(0\leq n\leq10^{18})\\
&出力:X
\end{align}
```
出典:yukicoder [No.502 階乗を計算するだけ](https://yukicoder.me/problems/no/502)

これをACしているコードがぱっと見よく分からなかったのと、解説がどこにもなかったので記事として書いてみた。

#考えること
* 階乗の計算量は$O(n)$である。そのため、愚直に計算すると間に合わない。
* もし$n$が$1.0×10^8$程度に収まれば、階乗を計算することができる。
* 途中から階乗の計算を始めることができれば計算量を減らせる。
* $n$が$10^9+7$以上の時、$n$の値にかかわらず$X$は$0$になる。

##例1 n=1000000008
例えば、$n$が$10^9+8$だったとする。これを愚直にやると、計算量は$O(10^9)$となってしまう。
しかし、次のことが言える。

```math
\begin{align}
&n=10^9+8のとき、\\
&n! = (10^9+8)\times (10^9+7)\times \dots \times2\times1\\
&よって、n!\mod(10^9+7)=0\\
\end{align}
```

このことは、$n$が$10^9+7$より大きいとき常に成り立つ。なぜなら、そのときの$n!$には必ず$10^9+7$が含まれているから。つまり、$n!$は$(10^9+7)$の倍数であり、$n! \mod (10^9+7)$は$0$になる。

##例2 n=900000006
次に、$nが9.0\times10^8+6$だったとする。$n$が$10^9+7$より小さいので、階乗を計算する必要がある。しかし、計算量は$1.0\times10^8$を超えてしまうため、実行時間を減らさないと計算できない。
もし、$(9.0\times10^8)!\mod(10^9+7)$の値が分かっていれば、$X$は次のように計算でき、その計算回数は6回である。

```c++:factorial.cpp
#include<bits/stdc++.h>
#include<iostream>
using namespace std;

int main(){
	long long n = 900000006;

    //事前に求めた9.0*10^8%10^9+7の答え
	long long catche = 586445753;

	long long ans = catche;
	for(long long i=900000001;i<=n;i++){
		ans = ans * i % mod;
	}
	cout<<ans<<endl;
}
```

```:output
983987424
```

ここでは、次のような計算を実行している。

```math
\begin{align}
&(9.0\times10^8)!\mod(10^9+7)=586445753のとき、\\
&(9.0\times10^8+6)!\mod(10^9+7)\\
&=\left\{586445753\times(9.0\times10^8+1)\times(9.0\times10^8+2)\times\\
\dots\\
\times(9.0\times10^8+6)\right\}\mod(10^9+7)\\
\end{align}
```

また、途中でオーバーフローが起きないように、掛け算をするたびにmodを計算している。
このようにして、$n$が$9.0\times10^8$より大きいとき、$9.0\times10^8$を起点とすることで、計算量を削減できる。階乗は$1.0\times10^8$回までは計算可能なので、$n$が$10.0\times10^8$に達するまでならこの方法が使える。

#解法
以上の考察により、ある$n$が与えられたとき、うまく起点を決めてやれば$1.0\times10^8$回までの計算で$n!\mod(10^9+7)$を求めることができる。そのためには、起点は$1.0\times10^8から10^8$ずつの幅で設定する必要がある。
つまり、$(1.0\times10^8)!\mod(10^9+7)$、$(2.0\times10^8)!\mod(10^9+7)$、$\dots$、$(1.0\times10^9)!\mod(10^9+7)$の値をそれぞれキャッシュとして事前に持たせておき、それを起点として計算することで計算量の削減ができるのである。

```c++:answer.cpp
int main(){
	long long n;
	cin>>n;

	long long mod = 1000000007;

	if(n==0){
		cout<<1<<endl;
		return 0;
	}
	//nが1000000007以上ならXは0になる
	if(n>=mod){
		cout<<0<<endl;
		return 0;
	}

	long long catche_list[11]={1,
			927880474, //100000000!%mod
			933245637, //200000000!%mod
			668123525, //300000000!%mod
			429277690, //400000000!%mod
			733333339, //500000000!%mod
			724464507, //600000000!%mod
			957939114, //700000000!%mod
			203191898, //800000000!%mod
			586445753, //900000000!%mod
			698611116, //1000000000!%mod
			};

	//nを10^8で割った商がcatche_listのインデックスになり起点が求まる
	long long start = n/100000000;
	long long ans = catche_list[start];

	//起点から階乗の計算を始める
	for(long long i=start*100000000+1;i<=n;i++){
		ans = ans * i % mod;
	}
	cout<<ans<<endl;

	return 0;
}
```

# キャッシュを求める
最後に、キャッシュを求めるためのコードを掲載する。
ここではmodを$10^9+7$、起点の幅を$10^8$としている。これは問題の設定や計算時間によって適宜変える必要がある。

```c++:make_catche.cpp
int main(){
	long long mod=1000000007;
	long long a=1;
	cout<<"{1,"<<endl;;
	for(long long i=1;i<mod;i++){
		a = a*i%mod;
		if(i%100000000==0){
			cout<<a<<","<<endl;
		}
	}
	cout<<"}"<<endl;
}
```

```:output
{1,
927880474,
933245637,
668123525,
429277690,
733333339,
724464507,
957939114,
203191898,
586445753,
698611116,
}
```

#まとめ
大きな数の階乗のmodは、事前にキャッシュを求めておくことで計算量を削減できる。
キャッシュの幅はc++であれば$1.0\times10^8$で設定すれば、2000ms以内に計算できる。
この概念、名前がついていないのだろうか？メモ化再帰の亜種？