#164163 (C++14) No.502 階乗を計算するだけ

提出ソース

結果

問題	No.502 階乗を計算するだけ
ユーザー	anta
提出日時	2017-04-07 22:29:13
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	11 ms / 1,000 ms
コード長	15,233 bytes
コンパイル時間	2,335 ms
コンパイル使用メモリ	177,896 KB
実行使用メモリ	6,948 KB
最終ジャッジ日時	2024-07-16 00:55:31
合計ジャッジ時間	3,779 ms
ジャッジサーバーID （参考情報）	judge5 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	2 ms 6,944 KB
testcase_04	AC	2 ms 6,940 KB
testcase_05	AC	2 ms 6,940 KB
testcase_06	AC	2 ms 6,944 KB
testcase_07	AC	2 ms 6,944 KB
testcase_08	AC	2 ms 6,940 KB
testcase_09	AC	2 ms 6,940 KB
testcase_10	AC	2 ms 6,940 KB
testcase_11	AC	2 ms 6,940 KB
testcase_12	AC	2 ms 6,940 KB
testcase_13	AC	2 ms 6,944 KB
testcase_14	AC	2 ms 6,940 KB
testcase_15	AC	2 ms 6,940 KB
testcase_16	AC	2 ms 6,940 KB
testcase_17	AC	2 ms 6,944 KB
testcase_18	AC	2 ms 6,944 KB
testcase_19	AC	2 ms 6,940 KB
testcase_20	AC	2 ms 6,940 KB
testcase_21	AC	1 ms 6,948 KB
testcase_22	AC	6 ms 6,940 KB
testcase_23	AC	3 ms 6,944 KB
testcase_24	AC	4 ms 6,940 KB
testcase_25	AC	2 ms 6,944 KB
testcase_26	AC	4 ms 6,944 KB
testcase_27	AC	3 ms 6,940 KB
testcase_28	AC	3 ms 6,940 KB
testcase_29	AC	2 ms 6,940 KB
testcase_30	AC	6 ms 6,940 KB
testcase_31	AC	3 ms 6,944 KB
testcase_32	AC	2 ms 6,940 KB
testcase_33	AC	11 ms 6,940 KB
testcase_34	AC	7 ms 6,940 KB
testcase_35	AC	11 ms 6,944 KB
testcase_36	AC	7 ms 6,940 KB
testcase_37	AC	11 ms 6,948 KB
testcase_38	AC	3 ms 6,940 KB
testcase_39	AC	5 ms 6,944 KB
testcase_40	AC	9 ms 6,940 KB
testcase_41	AC	2 ms 6,940 KB
testcase_42	AC	2 ms 6,940 KB
testcase_43	AC	2 ms 6,940 KB
testcase_44	AC	2 ms 6,940 KB
testcase_45	AC	2 ms 6,944 KB
testcase_46	AC	2 ms 6,940 KB
testcase_47	AC	2 ms 6,940 KB
testcase_48	AC	2 ms 6,944 KB
testcase_49	AC	2 ms 6,944 KB
testcase_50	AC	2 ms 6,940 KB
testcase_51	AC	2 ms 6,944 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if (x < y) x = y; }


template<int MOD>
struct ModInt {
	static const int Mod = MOD;
	unsigned x;
	ModInt() : x(0) { }
	ModInt(signed sig) { int sigt = sig % MOD; if (sigt < 0) sigt += MOD; x = sigt; }
	ModInt(signed long long sig) { int sigt = sig % MOD; if (sigt < 0) sigt += MOD; x = sigt; }
	int get() const { return (int)x; }

	ModInt &operator+=(ModInt that) { if ((x += that.x) >= MOD) x -= MOD; return *this; }
	ModInt &operator-=(ModInt that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
	ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }
	ModInt &operator/=(ModInt that) { return *this *= that.inverse(); }

	ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
	ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
	ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
	ModInt operator/(ModInt that) const { return ModInt(*this) /= that; }

	ModInt inverse() const {
		signed a = x, b = MOD, u = 1, v = 0;
		while (b) {
			signed t = a / b;
			a -= t * b; std::swap(a, b);
			u -= t * v; std::swap(u, v);
		}
		if (u < 0) u += Mod;
		ModInt res; res.x = (unsigned)u;
		return res;
	}
};
template<int MOD> ModInt<MOD> operator^(ModInt<MOD> a, unsigned long long k) {
	ModInt<MOD> r = 1;
	while (k) {
		if (k & 1) r *= a;
		a *= a;
		k >>= 1;
	}
	return r;
}
typedef ModInt<1000000007> mint;

int digitsMod(char s[], int n, int m) {
	int x = 0; long long pow10 = 1;
	for (int i = n - 1; i >= 0; i --) {
		if ((x += pow10 * (s[i] - '0') % m) >= m) x -= m;
		pow10 = pow10 * 10 % m;
	}
	return x;
}

template<typename T, int VALUES>
T computeWithUmekomi(const T(&ume)[VALUES], unsigned long long N, unsigned interval = 1U << 24) {
	unsigned long long idx = N / interval;
	if (idx >= VALUES) {
		cerr << "computeWithUmekomi: N >= " << interval * VALUES << endl;
		idx = VALUES - 1;
	}
	T t = ume[idx];
	unsigned i = (unsigned)(N - idx * interval);
	while (i > 0) {
		t.step();
		i --;
	}
	return t;
}

struct FactorialMotInt {
	int i; mint cnt;
	static FactorialMotInt init() {
		FactorialMotInt t = { 0, 1 };
		return t;
	}
	inline void step() {
		cnt *= ++ i;
	}
	friend ostream &operator<<(ostream &o, const FactorialMotInt &t) {
		return o << "{" << t.i << "," << t.cnt.get() << "}";
	}
	mint get() const { return cnt; }
};

struct FactorialMotInt ume[501] = {
	{ 0,1 },{ 2000000,578095319 },{ 4000000,259081142 },{ 6000000,316220877 },{ 8000000,251368199 },{ 10000000,682498929 },{ 12000000,95936601 },{ 14000000,167332441 },
	{ 16000000,336060741 },{ 18000000,626497524 },{ 20000000,491101308 },{ 22000000,565768255 },{ 24000000,968999 },{ 26000000,638587686 },{ 28000000,19426633 },{ 30000000,76479948 },
	{ 32000000,842267748 },{ 34000000,485348706 },{ 36000000,544075857 },{ 38000000,798967520 },{ 40000000,723816384 },{ 42000000,721996174 },{ 44000000,323604647 },{ 46000000,398699886 },
	{ 48000000,294587621 },{ 50000000,67347853 },{ 52000000,196447201 },{ 54000000,228338256 },{ 56000000,762479457 },{ 58000000,811667359 },{ 60000000,27368307 },{ 62000000,59469516 },
	{ 64000000,766196482 },{ 66000000,86609485 },{ 68000000,340941507 },{ 70000000,625544428 },{ 72000000,808412394 },{ 74000000,585237443 },{ 76000000,361786913 },{ 78000000,595143852 },
	{ 80000000,199888908 },{ 82000000,579691190 },{ 84000000,459188207 },{ 86000000,439729802 },{ 88000000,899297830 },{ 90000000,888050723 },{ 92000000,736550105 },{ 94000000,85990869 },
	{ 96000000,56305184 },{ 98000000,168891766 },{ 100000000,927880474 },{ 102000000,934814019 },{ 104000000,567277637 },{ 106000000,44930135 },{ 108000000,47401357 },{ 110000000,281863274 },
	{ 112000000,692636218 },{ 114000000,14235602 },{ 116000000,400295761 },{ 118000000,421835306 },{ 120000000,661224977 },{ 122000000,168203998 },{ 124000000,544064410 },{ 126000000,583967898 },
	{ 128000000,751231582 },{ 130000000,623534362 },{ 132000000,243276029 },{ 134000000,60050552 },{ 136000000,395891998 },{ 138000000,159554990 },{ 140000000,970055531 },{ 142000000,487998999 },
	{ 144000000,82104855 },{ 146000000,513365505 },{ 148000000,1559745 },{ 150000000,261384175 },{ 152000000,323214113 },{ 154000000,444090941 },{ 156000000,80729842 },{ 158000000,664989237 },
	{ 160000000,195888993 },{ 162000000,457882808 },{ 164000000,212938473 },{ 166000000,827544702 },{ 168000000,677711203 },{ 170000000,66404266 },{ 172000000,195290384 },{ 174000000,349551356 },
	{ 176000000,83489485 },{ 178000000,52167191 },{ 180000000,547665832 },{ 182000000,350016754 },{ 184000000,296269301 },{ 186000000,23015220 },{ 188000000,748566338 },{ 190000000,109838563 },
	{ 192000000,105574531 },{ 194000000,542432219 },{ 196000000,325636655 },{ 198000000,630621321 },{ 200000000,933245637 },{ 202000000,238971581 },{ 204000000,557301633 },{ 206000000,848952161 },
	{ 208000000,925152039 },{ 210000000,724691727 },{ 212000000,238087006 },{ 214000000,910291942 },{ 216000000,492237273 },{ 218000000,834860913 },{ 220000000,368925948 },{ 222000000,740594930 },
	{ 224000000,806047532 },{ 226000000,172115341 },{ 228000000,116261993 },{ 230000000,268838846 },{ 232000000,243624360 },{ 234000000,481661251 },{ 236000000,95182730 },{ 238000000,115435332 },
	{ 240000000,136026497 },{ 242000000,710729672 },{ 244000000,366384665 },{ 246000000,270239666 },{ 248000000,79874094 },{ 250000000,112390913 },{ 252000000,103056890 },{ 254000000,339464594 },
	{ 256000000,108312174 },{ 258000000,479334442 },{ 260000000,135498044 },{ 262000000,591048681 },{ 264000000,353339603 },{ 266000000,839849206 },{ 268000000,736265527 },{ 270000000,217544623 },
	{ 272000000,618898635 },{ 274000000,380858207 },{ 276000000,898554793 },{ 278000000,54062950 },{ 280000000,419363534 },{ 282000000,160398980 },{ 284000000,990918946 },{ 286000000,450718279 },
	{ 288000000,648991369 },{ 290000000,500780548 },{ 292000000,39052406 },{ 294000000,460373282 },{ 296000000,461415770 },{ 298000000,643638805 },{ 300000000,668123525 },{ 302000000,673464765 },
	{ 304000000,199866123 },{ 306000000,841799766 },{ 308000000,504962686 },{ 310000000,128487469 },{ 312000000,299172297 },{ 314000000,577786541 },{ 316000000,773206631 },{ 318000000,204355779 },
	{ 320000000,30977140 },{ 322000000,363172638 },{ 324000000,472935553 },{ 326000000,587220627 },{ 328000000,793270300 },{ 330000000,522049725 },{ 332000000,335416359 },{ 334000000,472012302 },
	{ 336000000,332139472 },{ 338000000,464599136 },{ 340000000,309058615 },{ 342000000,580204973 },{ 344000000,954840109 },{ 346000000,895609896 },{ 348000000,836813268 },{ 350000000,386027524 },
	{ 352000000,724205533 },{ 354000000,715247054 },{ 356000000,830567832 },{ 358000000,68409439 },{ 360000000,189239124 },{ 362000000,943653305 },{ 364000000,811056092 },{ 366000000,825132993 },
	{ 368000000,985084650 },{ 370000000,148528617 },{ 372000000,882148737 },{ 374000000,701445829 },{ 376000000,302177126 },{ 378000000,241107368 },{ 380000000,940567523 },{ 382000000,325334066 },
	{ 384000000,115312728 },{ 386000000,218129285 },{ 388000000,180002392 },{ 390000000,917084264 },{ 392000000,435327356 },{ 394000000,421623838 },{ 396000000,59883031 },{ 398000000,79716267 },
	{ 400000000,429277690 },{ 402000000,316486674 },{ 404000000,940338439 },{ 406000000,940524812 },{ 408000000,833550543 },{ 410000000,996164327 },{ 412000000,697611981 },{ 414000000,274192146 },
	{ 416000000,925347821 },{ 418000000,893732627 },{ 420000000,358655417 },{ 422000000,581830879 },{ 424000000,347046911 },{ 426000000,125354499 },{ 428000000,247662371 },{ 430000000,568392357 },
	{ 432000000,209244402 },{ 434000000,149586983 },{ 436000000,309134554 },{ 438000000,263053337 },{ 440000000,780072518 },{ 442000000,990826116 },{ 444000000,155569943 },{ 446000000,711553356 },
	{ 448000000,451373308 },{ 450000000,462639908 },{ 452000000,654611901 },{ 454000000,41815820 },{ 456000000,675258797 },{ 458000000,934281721 },{ 460000000,275105629 },{ 462000000,325912072 },
	{ 464000000,252551589 },{ 466000000,554917439 },{ 468000000,754363835 },{ 470000000,909210595 },{ 472000000,719566487 },{ 474000000,424989675 },{ 476000000,50590510 },{ 478000000,198768464 },
	{ 480000000,99199382 },{ 482000000,747407118 },{ 484000000,497196934 },{ 486000000,726997875 },{ 488000000,296229203 },{ 490000000,703397904 },{ 492000000,732868367 },{ 494000000,26031303 },
	{ 496000000,216665960 },{ 498000000,352946234 },{ 500000000,733333339 },{ 502000000,459878625 },{ 504000000,16634739 },{ 506000000,68718097 },{ 508000000,404206040 },{ 510000000,97830135 },
	{ 512000000,31131935 },{ 514000000,864326453 },{ 516000000,167831173 },{ 518000000,718498895 },{ 520000000,608823837 },{ 522000000,385388084 },{ 524000000,681756977 },{ 526000000,313132653 },
	{ 528000000,442795120 },{ 530000000,256141983 },{ 532000000,636578562 },{ 534000000,553033642 },{ 536000000,919273670 },{ 538000000,326686486 },{ 540000000,141827977 },{ 542000000,693305776 },
	{ 544000000,186576440 },{ 546000000,565456578 },{ 548000000,519397500 },{ 550000000,696628828 },{ 552000000,370732451 },{ 554000000,915265013 },{ 556000000,923043932 },{ 558000000,777901604 },
	{ 560000000,637939935 },{ 562000000,490676632 },{ 564000000,462528877 },{ 566000000,798895521 },{ 568000000,699767918 },{ 570000000,811575797 },{ 572000000,606870929 },{ 574000000,179111720 },
	{ 576000000,508038818 },{ 578000000,752550134 },{ 580000000,848924691 },{ 582000000,34629406 },{ 584000000,435904287 },{ 586000000,208184231 },{ 588000000,206330671 },{ 590000000,131772368 },
	{ 592000000,648711554 },{ 594000000,523696723 },{ 596000000,25058942 },{ 598000000,817928963 },{ 600000000,724464507 },{ 602000000,701453022 },{ 604000000,281230685 },{ 606000000,596949867 },
	{ 608000000,303076380 },{ 610000000,272814771 },{ 612000000,48824684 },{ 614000000,939889684 },{ 616000000,48527183 },{ 618000000,484458461 },{ 620000000,326159309 },{ 622000000,668422905 },
	{ 624000000,965656187 },{ 626000000,359960756 },{ 628000000,407934361 },{ 630000000,456152084 },{ 632000000,124804049 },{ 634000000,920251227 },{ 636000000,483924582 },{ 638000000,167087470 },
	{ 640000000,903466878 },{ 642000000,368114731 },{ 644000000,388728584 },{ 646000000,249153339 },{ 648000000,322908524 },{ 650000000,92255682 },{ 652000000,15570863 },{ 654000000,744158074 },
	{ 656000000,334326205 },{ 658000000,98349682 },{ 660000000,769795511 },{ 662000000,888146074 },{ 664000000,582627184 },{ 666000000,919419361 },{ 668000000,986708498 },{ 670000000,373745190 },
	{ 672000000,256853930 },{ 674000000,702823274 },{ 676000000,308186532 },{ 678000000,180350107 },{ 680000000,606241871 },{ 682000000,273712630 },{ 684000000,682189174 },{ 686000000,946867127 },
	{ 688000000,502371023 },{ 690000000,825871994 },{ 692000000,701506133 },{ 694000000,341779962 },{ 696000000,815463367 },{ 698000000,49187570 },{ 700000000,957939114 },{ 702000000,933376898 },
	{ 704000000,338121343 },{ 706000000,869630152 },{ 708000000,632627667 },{ 710000000,435887178 },{ 712000000,129621197 },{ 714000000,827722926 },{ 716000000,918513230 },{ 718000000,547838438 },
	{ 720000000,852304035 },{ 722000000,689189630 },{ 724000000,567033437 },{ 726000000,212842957 },{ 728000000,404149413 },{ 730000000,663307737 },{ 732000000,206282795 },{ 734000000,488906585 },
	{ 736000000,280700600 },{ 738000000,534279149 },{ 740000000,375297772 },{ 742000000,922377372 },{ 744000000,219932130 },{ 746000000,701050258 },{ 748000000,863002719 },{ 750000000,217598709 },
	{ 752000000,810551911 },{ 754000000,247844667 },{ 756000000,812283640 },{ 758000000,857241854 },{ 760000000,624148346 },{ 762000000,564827277 },{ 764000000,478982047 },{ 766000000,454039189 },
	{ 768000000,48562889 },{ 770000000,671734977 },{ 772000000,508831870 },{ 774000000,897162044 },{ 776000000,892168027 },{ 778000000,277714559 },{ 780000000,624500515 },{ 782000000,808691930 },
	{ 784000000,895205045 },{ 786000000,628829100 },{ 788000000,919717789 },{ 790000000,748510389 },{ 792000000,574455974 },{ 794000000,172096141 },{ 796000000,581418893 },{ 798000000,15391652 },
	{ 800000000,203191898 },{ 802000000,880691101 },{ 804000000,986598821 },{ 806000000,264688936 },{ 808000000,785804644 },{ 810000000,423951674 },{ 812000000,696623384 },{ 814000000,161960209 },
	{ 816000000,541120825 },{ 818000000,841656666 },{ 820000000,629786193 },{ 822000000,269571439 },{ 824000000,76770272 },{ 826000000,421943723 },{ 828000000,751040886 },{ 830000000,672850561 },
	{ 832000000,493689107 },{ 834000000,100228913 },{ 836000000,639655136 },{ 838000000,929893103 },{ 840000000,814362881 },{ 842000000,406024012 },{ 844000000,10065330 },{ 846000000,983737173 },
	{ 848000000,551060742 },{ 850000000,823845496 },{ 852000000,946421040 },{ 854000000,842203531 },{ 856000000,894247956 },{ 858000000,885362182 },{ 860000000,116667533 },{ 862000000,241427979 },
	{ 864000000,281804989 },{ 866000000,563796647 },{ 868000000,774625892 },{ 870000000,256473217 },{ 872000000,918860977 },{ 874000000,753513874 },{ 876000000,304644842 },{ 878000000,161362528 },
	{ 880000000,627655552 },{ 882000000,799289297 },{ 884000000,816701166 },{ 886000000,787113234 },{ 888000000,701220427 },{ 890000000,245795606 },{ 892000000,10475577 },{ 894000000,759404319 },
	{ 896000000,491466901 },{ 898000000,114495791 },{ 900000000,586445753 },{ 902000000,718623833 },{ 904000000,66547751 },{ 906000000,351472920 },{ 908000000,494166907 },{ 910000000,172114298 },
	{ 912000000,364380585 },{ 914000000,965683742 },{ 916000000,117483873 },{ 918000000,237120480 },{ 920000000,193781724 },{ 922000000,107141741 },{ 924000000,793307102 },{ 926000000,236455213 },
	{ 928000000,14162538 },{ 930000000,778983779 },{ 932000000,49389215 },{ 934000000,859637374 },{ 936000000,713258160 },{ 938000000,923333660 },{ 940000000,83868974 },{ 942000000,217298111 },
	{ 944000000,176966527 },{ 946000000,105359006 },{ 948000000,10430738 },{ 950000000,315103615 },{ 952000000,708233401 },{ 954000000,946149627 },{ 956000000,281329488 },{ 958000000,31503476 },
	{ 960000000,965785236 },{ 962000000,916291845 },{ 964000000,899946391 },{ 966000000,512634493 },{ 968000000,121000338 },{ 970000000,492741665 },{ 972000000,165393390 },{ 974000000,917041303 },
	{ 976000000,741626808 },{ 978000000,536841269 },{ 980000000,377329025 },{ 982000000,859917803 },{ 984000000,373451745 },{ 986000000,823495900 },{ 988000000,73146164 },{ 990000000,847549272 },
	{ 992000000,646654592 },{ 994000000,205951465 },{ 996000000,780882948 },{ 998000000,598245292 },{ 1000000000,698611116 },
};


const int Interval = 2000000;
mint factorial(int n) {
	return computeWithUmekomi(ume, n, Interval).get();
}

int main() {
	long long n;
	while (~scanf("%lld", &n)) {
		mint ans = n >= mint::Mod ? 0 : factorial((int)n);
		printf("%d\n", ans.get());
	}
	return 0;
}

yukicoder

結果

テストケース

ソースコード