kmjp's blog

競技プログラミング参加記です

yukicoder : No.502 階乗を計算するだけ

放送中コード量に言及していることに気付くべきだった…。
http://yukicoder.me/problems/no/502

問題

入力Nに対し、N! mod (10^9+7)を求めよ。

解法

Nが(10^9+7)以上ならN!の剰余は0になる。
それ以外の場合、最悪ケースN=(10^9+6)を計算してみると、PCの性能にもよるが10秒位で終わる。

…ということでいったん手元で10秒分計算し、コードに途中経過を埋め込もう。
以下は配列Aに10^7回ごとの計算の途中経過を格納している。

ll N;
ll mo=1000000007;

ll A[]={
1              ,
682498929      ,
491101308      ,
76479948      ,
(略)
492741665      ,
377329025      ,
847549272      ,
698611116      ,
};

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	if(N>=mo) {
		cout<<0<<endl;
		return;
	}
	else {
		ll ret=A[N/10000000];
		for(i=N/10000000*10000000+1;i<=N;i++) {
			ret=ret*i%mo;
		}
		cout<<ret<<endl;
	}
	
}

まとめ

「なんでみんなこんなスラスラ解いているんだ?」と思ってコード量を見て気づきました。