結果
問題 | No.502 階乗を計算するだけ |
ユーザー |
![]() |
提出日時 | 2017-04-07 22:34:21 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 21 ms / 1,000 ms |
コード長 | 7,736 bytes |
コンパイル時間 | 1,341 ms |
コンパイル使用メモリ | 171,176 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-16 01:03:45 |
合計ジャッジ時間 | 2,666 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 52 |
ソースコード
#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))// modconst 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;}