結果

問題 No.502 階乗を計算するだけ
ユーザー rickythetarickytheta
提出日時 2017-04-07 22:34:21
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 23 ms / 1,000 ms
コード長 7,736 bytes
コンパイル時間 1,380 ms
コンパイル使用メモリ 157,720 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-23 00:32:35
合計ジャッジ時間 3,485 ms
ジャッジサーバーID
(参考情報)
judge15 / judge12
このコードへのチャレンジ(β)

テストケース

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

ソースコード

diff #

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;

int main(){
  ll n;
  cin>>n;
  if(n >= MOD){
    puts("0");
    return 0;
  }
  if(false){
    ll x = 1;
    FOR(i,1,MOD){
      x = x * i % MOD;
      if(i%(MOD/256)==0){
        printf("M[%d] = %lld;\n",i,x);
      }
    }
  }else{
    map<int,int> M;
    M[0] = 1;
M[3906250] = 714469525;
M[7812500] = 411278297;
M[11718750] = 518244246;
M[15625000] = 26078120;
M[19531250] = 24466848;
M[23437500] = 589240816;
M[27343750] = 842272651;
M[31250000] = 86516931;
M[35156250] = 819748105;
M[39062500] = 658463604;
M[42968750] = 48006566;
M[46875000] = 752391549;
M[50781250] = 510863510;
M[54687500] = 686384505;
M[58593750] = 513692786;
M[62500000] = 498440078;
M[66406250] = 150354137;
M[70312500] = 269174995;
M[74218750] = 555861545;
M[78125000] = 623685432;
M[82031250] = 348958758;
M[85937500] = 96141114;
M[89843750] = 498679724;
M[93750000] = 646617630;
M[97656250] = 701779706;
M[101562500] = 28291357;
M[105468750] = 856945555;
M[109375000] = 238082618;
M[113281250] = 827665801;
M[117187500] = 786430071;
M[121093750] = 232018338;
M[125000000] = 935080803;
M[128906250] = 836252615;
M[132812500] = 586228462;
M[136718750] = 805287637;
M[140625000] = 21945719;
M[144531250] = 614220209;
M[148437500] = 837801456;
M[152343750] = 490027773;
M[156250000] = 409109146;
M[160156250] = 651216427;
M[164062500] = 303124227;
M[167968750] = 951221398;
M[171875000] = 364701337;
M[175781250] = 795538962;
M[179687500] = 148350569;
M[183593750] = 136724157;
M[187500000] = 670821828;
M[191406250] = 897990080;
M[195312500] = 265505287;
M[199218750] = 296668617;
M[203125000] = 830131719;
M[207031250] = 51439824;
M[210937500] = 314385204;
M[214843750] = 916351987;
M[218750000] = 574749701;
M[222656250] = 892699578;
M[226562500] = 227183216;
M[230468750] = 762745094;
M[234375000] = 420234887;
M[238281250] = 921779498;
M[242187500] = 818166921;
M[246093750] = 364513389;
M[250000000] = 112390913;
M[253906250] = 975334107;
M[257812500] = 595648930;
M[261718750] = 578268546;
M[265625000] = 458508472;
M[269531250] = 748449353;
M[273437500] = 187805536;
M[277343750] = 229089764;
M[281250000] = 643455042;
M[285156250] = 141290483;
M[289062500] = 832095631;
M[292968750] = 150755137;
M[296875000] = 28936598;
M[300781250] = 782206916;
M[304687500] = 264667016;
M[308593750] = 502122216;
M[312500000] = 464643614;
M[316406250] = 644173348;
M[320312500] = 693083025;
M[324218750] = 407897111;
M[328125000] = 708326952;
M[332031250] = 520689513;
M[335937500] = 209978716;
M[339843750] = 51238131;
M[343750000] = 298641073;
M[347656250] = 718646507;
M[351562500] = 421728413;
M[355468750] = 793551739;
M[359375000] = 65645502;
M[363281250] = 840794725;
M[367187500] = 622424851;
M[371093750] = 897030045;
M[375000000] = 529726489;
M[378906250] = 824961638;
M[382812500] = 963908580;
M[386718750] = 148560148;
M[390625000] = 105776888;
M[394531250] = 135442356;
M[398437500] = 63401518;
M[402343750] = 228259732;
M[406250000] = 872682299;
M[410156250] = 38741196;
M[414062500] = 155811519;
M[417968750] = 347546650;
M[421875000] = 933295133;
M[425781250] = 436450952;
M[429687500] = 803256912;
M[433593750] = 463511049;
M[437500000] = 835720092;
M[441406250] = 620338862;
M[445312500] = 509312849;
M[449218750] = 139766062;
M[453125000] = 426286887;
M[457031250] = 40872698;
M[460937500] = 214310502;
M[464843750] = 131967328;
M[468750000] = 70371679;
M[472656250] = 89439658;
M[476562500] = 825326374;
M[480468750] = 92753025;
M[484375000] = 591062021;
M[488281250] = 439887896;
M[492187500] = 419061828;
M[496093750] = 392568716;
M[500000000] = 733333339;
M[503906250] = 766632667;
M[507812500] = 733878273;
M[511718750] = 273687215;
M[515625000] = 406828148;
M[519531250] = 495141350;
M[523437500] = 319527924;
M[527343750] = 443395497;
M[531250000] = 379850306;
M[535156250] = 547227992;
M[539062500] = 268500523;
M[542968750] = 138016354;
M[546875000] = 556596747;
M[550781250] = 902620074;
M[554687500] = 585393176;
M[558593750] = 592401312;
M[562500000] = 404533909;
M[566406250] = 691479197;
M[570312500] = 734297155;
M[574218750] = 38654771;
M[578125000] = 958501915;
M[582031250] = 706116312;
M[585937500] = 408885251;
M[589843750] = 540983562;
M[593750000] = 969021396;
M[597656250] = 212851067;
M[601562500] = 607605949;
M[605468750] = 906543777;
M[609375000] = 472325230;
M[613281250] = 357247016;
M[617187500] = 685303163;
M[621093750] = 812801438;
M[625000000] = 44135644;
M[628906250] = 79659424;
M[632812500] = 723971607;
M[636718750] = 509131674;
M[640625000] = 315385078;
M[644531250] = 224877938;
M[648437500] = 974901805;
M[652343750] = 601198190;
M[656250000] = 254834284;
M[660156250] = 497082802;
M[664062500] = 221704894;
M[667968750] = 198421659;
M[671875000] = 624015727;
M[675781250] = 284596661;
M[679687500] = 341245120;
M[683593750] = 98451570;
M[687500000] = 430345388;
M[691406250] = 310121083;
M[695312500] = 167380627;
M[699218750] = 561947482;
M[703125000] = 642821983;
M[707031250] = 958216230;
M[710937500] = 670006283;
M[714843750] = 692662800;
M[718750000] = 584987581;
M[722656250] = 514902053;
M[726562500] = 776683072;
M[730468750] = 348401723;
M[734375000] = 254009038;
M[738281250] = 873361523;
M[742187500] = 5052678;
M[746093750] = 710599610;
M[750000000] = 217598709;
M[753906250] = 419344276;
M[757812500] = 687914578;
M[761718750] = 272383531;
M[765625000] = 840892704;
M[769531250] = 379279013;
M[773437500] = 9687821;
M[777343750] = 733935156;
M[781250000] = 680778659;
M[785156250] = 219395009;
M[789062500] = 230368570;
M[792968750] = 224253999;
M[796875000] = 406075920;
M[800781250] = 820372682;
M[804687500] = 216155688;
M[808593750] = 510283130;
M[812500000] = 807827182;
M[816406250] = 678976140;
M[820312500] = 427874355;
M[824218750] = 658469834;
M[828125000] = 974657241;
M[832031250] = 287150287;
M[835937500] = 955461108;
M[839843750] = 768960774;
M[843750000] = 757452839;
M[847656250] = 455030985;
M[851562500] = 926551075;
M[855468750] = 30413763;
M[859375000] = 692179125;
M[863281250] = 558246076;
M[867187500] = 166326785;
M[871093750] = 657332680;
M[875000000] = 393556719;
M[878906250] = 835525623;
M[882812500] = 170012974;
M[886718750] = 180181136;
M[890625000] = 223796635;
M[894531250] = 72032685;
M[898437500] = 932982797;
M[902343750] = 38863204;
M[906250000] = 861932447;
M[910156250] = 690607104;
M[914062500] = 85853649;
M[917968750] = 994010090;
M[921875000] = 33723946;
M[925781250] = 73062179;
M[929687500] = 626632507;
M[933593750] = 567110585;
M[937500000] = 131731042;
M[941406250] = 143630897;
M[945312500] = 420165676;
M[949218750] = 502721802;
M[953125000] = 982197935;
M[957031250] = 695722157;
M[960937500] = 641538576;
M[964843750] = 237181745;
M[968750000] = 912934355;
M[972656250] = 473889915;
M[976562500] = 385222994;
M[980468750] = 894124456;
M[984375000] = 273780895;
M[988281250] = 472901645;
M[992187500] = 598653456;
M[996093750] = 274108493;
M[1000000000] = 698611116;

    map<int,int>::iterator it = M.upper_bound(n);
    it--;
    int i = it->first;
    ll v = it->second;
    while(i < n){
      i++;
      v = v * i % MOD;
    }
    printf("%lld\n",v);
  }
  return 0;
}
0