結果

問題 No.502 階乗を計算するだけ
ユーザー どららどらら
提出日時 2017-04-08 01:00:03
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,876 bytes
コンパイル時間 1,409 ms
コンパイル使用メモリ 163,760 KB
実行使用メモリ 4,504 KB
最終ジャッジ日時 2023-09-23 03:19:21
合計ジャッジ時間 3,868 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 1 ms
4,376 KB
testcase_08 AC 1 ms
4,380 KB
testcase_09 AC 1 ms
4,380 KB
testcase_10 AC 2 ms
4,376 KB
testcase_11 AC 2 ms
4,380 KB
testcase_12 AC 2 ms
4,380 KB
testcase_13 AC 1 ms
4,376 KB
testcase_14 AC 2 ms
4,380 KB
testcase_15 AC 1 ms
4,376 KB
testcase_16 AC 2 ms
4,380 KB
testcase_17 AC 2 ms
4,380 KB
testcase_18 AC 1 ms
4,376 KB
testcase_19 AC 2 ms
4,380 KB
testcase_20 AC 2 ms
4,376 KB
testcase_21 AC 1 ms
4,376 KB
testcase_22 AC 17 ms
4,380 KB
testcase_23 AC 6 ms
4,380 KB
testcase_24 AC 12 ms
4,380 KB
testcase_25 AC 3 ms
4,376 KB
testcase_26 AC 7 ms
4,380 KB
testcase_27 AC 5 ms
4,376 KB
testcase_28 AC 6 ms
4,376 KB
testcase_29 AC 4 ms
4,376 KB
testcase_30 AC 16 ms
4,376 KB
testcase_31 AC 9 ms
4,376 KB
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
testcase_39 WA -
testcase_40 WA -
testcase_41 RE -
testcase_42 RE -
testcase_43 AC 23 ms
4,380 KB
testcase_44 AC 6 ms
4,380 KB
testcase_45 WA -
testcase_46 AC 23 ms
4,376 KB
testcase_47 AC 19 ms
4,376 KB
testcase_48 AC 28 ms
4,376 KB
testcase_49 AC 24 ms
4,376 KB
testcase_50 AC 23 ms
4,380 KB
testcase_51 AC 20 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

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