結果

問題 No.502 階乗を計算するだけ
コンテスト
ユーザー どらら
提出日時 2017-04-08 01:00:03
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,876 bytes
コンパイル時間 1,358 ms
コンパイル使用メモリ 166,396 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-16 03:35:35
合計ジャッジ時間 3,155 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 40 WA * 10 RE * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

#define MOD 1000000007
int fact[]={
1,
641102369,
578095319,
5832229,
259081142,
974067448,
316220877,
690120224,
251368199,
980250487,
682498929,
134623568,
95936601,
933097914,
167332441,
598816162,
336060741,
248744620,
626497524,
288843364,
491101308,
245341950,
565768255,
246899319,
968999,
586350670,
638587686,
881746146,
19426633,
850500036,
76479948,
268124147,
842267748,
886294336,
485348706,
463847391,
544075857,
898187927,
798967520,
82926604,
723816384,
156530778,
721996174,
299085602,
323604647,
172827403,
398699886,
530389102,
294587621,
813805606,
67347853,
497478507,
196447201,
722054885,
228338256,
407719831,
762479457,
746536789,
811667359,
778773518,
27368307,
438371670,
59469516,
5974669,
766196482,
606322308,
86609485,
889750731,
340941507,
371263376,
625544428,
788878910,
808412394,
996952918,
585237443,
1669644,
361786913,
480748381,
595143852,
837229828,
199888908,
526807168,
579691190,
145404005,
459188207,
534491822,
439729802,
840398449,
899297830,
235861787,
888050723,
656116726,
736550105,
440902696,
85990869,
884343068,
56305184,
973478770,
168891766,
804805577,
927880474
};

ll mod_fact(ll n, ll p){
  ll res = 1;
  for(ll i=n; i>0; i--){
    if(i%1000000==0){
      res *= fact[i/1000000LL];
      res %= p;
      break;
    }else{
      res = (res*i)%p;
    }
  }
  return res;
}
ll mod_fact_fast(ll n, ll p){
  ll res = 1;
  while(n>0){
    ll m = n%p;
    res *= mod_fact(m, p);
    if((n/=p)%2>0) res = p-res;
  }
  return res;
}

int main(){
  ll n;
  cin >> n;

  cout << mod_fact_fast(n, MOD) << endl;
  
  return 0;
}
0