#332861 (C++14) No.3048 Order and Harmony

提出ソース

結果

問題	No.3048 Order and Harmony
ユーザー	FF256grhy
提出日時	2019-04-01 22:07:11
言語	C++14 (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	173 ms / 2,000 ms
コード長	15,223 bytes
コンパイル時間	2,944 ms
コンパイル使用メモリ	246,844 KB
実行使用メモリ	4,380 KB
最終ジャッジ日時	2023-08-18 01:14:34
合計ジャッジ時間	7,950 ms
ジャッジサーバーID （参考情報）	judge15 / judge14

このコードへのチャレンジ（β）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,376 KB
testcase_01	AC	1 ms 4,380 KB
testcase_02	AC	18 ms 4,380 KB
testcase_03	AC	89 ms 4,380 KB
testcase_04	AC	2 ms 4,376 KB
testcase_05	AC	2 ms 4,380 KB
testcase_06	AC	11 ms 4,380 KB
testcase_07	AC	2 ms 4,376 KB
testcase_08	AC	12 ms 4,380 KB
testcase_09	AC	1 ms 4,376 KB
testcase_10	AC	12 ms 4,376 KB
testcase_11	AC	5 ms 4,376 KB
testcase_12	AC	2 ms 4,376 KB
testcase_13	AC	2 ms 4,380 KB
testcase_14	AC	2 ms 4,376 KB
testcase_15	AC	18 ms 4,380 KB
testcase_16	AC	2 ms 4,376 KB
testcase_17	AC	1 ms 4,376 KB
testcase_18	AC	2 ms 4,376 KB
testcase_19	AC	19 ms 4,380 KB
testcase_20	AC	15 ms 4,380 KB
testcase_21	AC	14 ms 4,376 KB
testcase_22	AC	8 ms 4,380 KB
testcase_23	AC	1 ms 4,376 KB
testcase_24	AC	2 ms 4,380 KB
testcase_25	AC	6 ms 4,376 KB
testcase_26	AC	44 ms 4,376 KB
testcase_27	AC	104 ms 4,380 KB
testcase_28	AC	96 ms 4,376 KB
testcase_29	AC	1 ms 4,376 KB
testcase_30	AC	62 ms 4,376 KB
testcase_31	AC	1 ms 4,376 KB
testcase_32	AC	82 ms 4,380 KB
testcase_33	AC	1 ms 4,376 KB
testcase_34	AC	23 ms 4,376 KB
testcase_35	AC	2 ms 4,376 KB
testcase_36	AC	153 ms 4,376 KB
testcase_37	AC	93 ms 4,380 KB
testcase_38	AC	123 ms 4,376 KB
testcase_39	AC	136 ms 4,376 KB
testcase_40	AC	14 ms 4,380 KB
testcase_41	AC	55 ms 4,376 KB
testcase_42	AC	114 ms 4,380 KB
testcase_43	AC	2 ms 4,380 KB
testcase_44	AC	135 ms 4,376 KB
testcase_45	AC	169 ms 4,380 KB
testcase_46	AC	161 ms 4,376 KB
testcase_47	AC	46 ms 4,376 KB
testcase_48	AC	48 ms 4,380 KB
testcase_49	AC	1 ms 4,376 KB
testcase_50	AC	21 ms 4,376 KB
testcase_51	AC	1 ms 4,376 KB
testcase_52	AC	2 ms 4,380 KB
testcase_53	AC	108 ms 4,376 KB
testcase_54	AC	2 ms 4,380 KB
testcase_55	AC	1 ms 4,376 KB
testcase_56	AC	28 ms 4,376 KB
testcase_57	AC	2 ms 4,380 KB
testcase_58	AC	1 ms 4,380 KB
testcase_59	AC	2 ms 4,376 KB
testcase_60	AC	45 ms 4,376 KB
testcase_61	AC	139 ms 4,376 KB
testcase_62	AC	105 ms 4,376 KB
testcase_63	AC	1 ms 4,376 KB
testcase_64	AC	173 ms 4,380 KB

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

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;
typedef long long   signed int LL;
typedef long long unsigned int LU;
#define incII(i, l, r) for(int i = (l)    ; i <= (r); ++i)
#define incID(i, l, r) for(int i = (l)    ; i <  (r); ++i)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); --i)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); --i)
#define inc(i, n)  incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define dec(i, n)  decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)
#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
template<typename T> bool setmin  (T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmax  (T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
LL mo(LL a, LL b) { assert(b > 0); a %= b; if(a < 0) { a += b; } return a; }
LL fl(LL a, LL b) { assert(b > 0); return (a > 0 ? a / b : (a - b + 1) / b); }
LL ce(LL a, LL b) { assert(b > 0); return (a < 0 ? a / b : (a + b - 1) / b); }
#define bit(b, i) (((b) >> (i)) & 1)
#define BC __builtin_popcountll
#define SC(T, v) static_cast<T>(v)
#define SI(v) SC(int, v.size())
#define SL(v) SC( LL, v.size())
#define RF(e, v) for(auto & e: v)
#define ei else if
#define UR assert(false)

// ---- ----

template<LL M> class ModInt {
private:
	LL v = 0;
public:
	ModInt() { }
	ModInt(LL vv) { setval(vv); }
	ModInt & setval(LL vv) { v = vv % M; if(v < 0) { v += M; } return (*this); }
	LL getval() const { return v; }
	ModInt & operator+=(const ModInt & b)       { return setval(v + b.v); }
	ModInt & operator-=(const ModInt & b)       { return setval(v - b.v); }
	ModInt & operator*=(const ModInt & b)       { return setval(v * b.v); }
	ModInt & operator/=(const ModInt & b)       { return setval(v * b.inv()); }
	ModInt & operator^=(            LU b)       { return setval(ex(v, b)); }
	ModInt   operator+ (                ) const { return ModInt(+v); }
	ModInt   operator- (                ) const { return ModInt(-v); }
	ModInt   operator+ (const ModInt & b) const { return ModInt(v + b.v); }
	ModInt   operator- (const ModInt & b) const { return ModInt(v - b.v); }
	ModInt   operator* (const ModInt & b) const { return ModInt(v * b.v); }
	ModInt   operator/ (const ModInt & b) const { return ModInt(v * b.inv()); }
	ModInt   operator^ (            LU b) const { return ModInt(ex(v, b)); }
	LL inv() const {
		LL x = (ex_gcd(v, M).FI + M) % M;
		assert(v * x % M == 1);
		return x;
	}
	LL ex(LL a, LU b) const {
		LL D = 64, x[64], y = 1;
		inc(i, D) { if((b >> i) == 0) { D = i; break; } }
		inc(i, D) { x[i] = (i == 0 ? a : x[i - 1] * x[i - 1]) % M; }
		inc(i, D) { if((b >> i) & 1) { (y *= x[i]) %= M; } }
		return y;
	}
	pair<LL, LL> ex_gcd(LL a, LL b) const {
		if(b == 0) { return MP(1, 0); }
		auto p = ex_gcd(b, a % b);
		return MP(p.SE, p.FI - (a / b) * p.SE);
	}
};
template<LL M> ModInt<M> operator+(LL a, const ModInt<M> & b) { return  b + a; }
template<LL M> ModInt<M> operator-(LL a, const ModInt<M> & b) { return -b + a; }
template<LL M> ModInt<M> operator*(LL a, const ModInt<M> & b) { return  b * a; }
template<LL M> ModInt<M> operator/(LL a, const ModInt<M> & b) { return  a * b.inv(); }
template<LL M> istream & operator>>(istream & is, ModInt<M> & b) { LL v; is >> v; b.setval(v); return is; }
template<LL M> ostream & operator<<(ostream & os, const ModInt<M> & b) { return (os << b.getval()); }

// ---- ----

typedef ModInt<1'000'000'007> MI;

MI a[] = { 1, 996692777, 192151600, 245687672, 303317497, 828782236, 225758344, 400451229, 969682025, 240306731, 908084721, 607546320, 284923739, 829810463, 668003095, 894469105, 401315780, 291841056, 427368398, 236829697, 486682686, 533328634, 253966590, 403350553, 775370360, 931771229, 200402559, 70599779, 58679838, 538975877, 712141386, 268923391, 670830993, 90005902, 754841810, 419067033, 668320258, 778642351, 915288676, 160520177, 632356321, 438505277, 568293197, 626702306, 964151785, 33381677, 129545199, 518517817, 34281045, 390380794, 3661409, 583417804, 629846475, 700537733, 779244208, 909331793, 674921426, 314754820, 566455901, 372400763, 340986487, 193346110, 677775998, 946216839, 436403968, 151972503, 354738506, 872705753, 300921411, 915793454, 406503987, 626362472, 945175639, 24026767, 215428938, 78095654, 173574, 648397850, 427739854, 220349572, 314530070, 292037739, 361256176, 682504006, 563026923, 36923237, 732057658, 642196378, 969334076, 47582912, 5260082, 710974748, 802368054, 348505205, 426596560, 503314767, 619187806, 506282842, 382917476, 470942674, 592883062, 170028190, 702187902, 5611654, 546052126, 972809893, 249049186, 817296111, 329719104, 572654585, 553478243, 907532292, 572539088, 644477702, 663220103, 915362704, 117672443, 837412970, 513676568, 808923512, 518966120, 518928703, 150907969, 648302439, 788223880, 451849423, 316713329, 392349123, 678840267, 252091087, 515351708, 647781185, 147582903, 823296737, 985959192, 468236180, 112669548, 994436365, 921905314, 592157810, 673794059, 620983750, 386764031, 547958693, 798539725, 819342573, 340685356, 407027944, 968036532, 364002114, 649627038, 890903806, 912947975, 794431833, 1595508, 253475558, 325649778, 591312170, 921054161, 88185282, 813746100, 662216406, 577283561, 57580793, 828992380, 632179962, 864056884, 228494491, 921089861, 369267366, 574534617, 121648900, 379009917, 573998781, 555126550, 800789350, 306149020, 56427039, 751054413, 884284782, 714442474, 887600123, 785075874, 313631500, 411102981, 980541422, 521231881, 381609024, 960886557, 376643154, 365614344, 877834823, 548703031, 868418317, 666688197, 564390938, 683720684, 524130865, 443779519, 282313091, 836415057, 763702490, 11133147, 66225197, 624861826, 380434489, 149832585, 903707203, 485879706, 607998705, 836193960, 13597302, 140655400, 699139884, 292404865, 195501908, 723865218, 78622912, 642679966, 733877589, 89241560, 546378306, 660503627, 240704224, 75775057, 424333059, 67162553, 672784585, 979542334, 293154658, 196539457, 181086142, 280319980, 378695442, 990034472, 626535687, 411523712, 322223168, 613174045, 530468253, 819706300, 108149034, 351462048, 232567612, 924576716, 662060859, 909665810, 511266815, 105318868, 940930884, 547167651, 312956117, 126656684, 960208877, 309793984, 955200145, 52255993, 220088230, 687279312, 446947299, 55594113, 194636345, 490406408, 840701344, 444484932, 865781610, 518584451, 855971259, 159802187, 608116924, 366092496, 609255452, 455512235, 473319098, 433045200, 975602830, 518078249, 491350226, 550644387, 582178963, 175806902, 453450326, 819541293, 621374853, 426449184, 532437990, 915635307, 701775999, 720443175, 568788849, 827211344, 751933202, 370315994, 115013568, 753333391, 64395922, 634631385, 232081602, 650155158, 877395191, 940400276, 227684030, 606765894, 226475666, 712304346, 922149932, 663313318, 18228977, 60619980, 91746201, 983402432, 233629972, 869278090, 672795263, 972324983, 621571935, 391703602, 665832795, 172338326, 352775796, 217479453, 800016699, 590579572, 261111412, 495770427, 664125655, 421095712, 599995715, 206896597, 838043034, 381147856, 711482938, 947282979, 718713411, 725591595, 990964763, 348938379, 525753212, 550901380, 975159183, 775310148, 582069505, 759746521, 890080202, 26018583, 340904340, 68714910, 937326527, 504676813, 436469890, 77954755, 538463698, 724347421, 80724093, 513184227, 98058876, 987081719, 965193153, 925181085, 167262970, 620333824, 65506595, 382756343, 393730229, 314140104, 442957476, 118782277, 44018429, 326661915, 46259282, 760459045, 107122021, 540410246, 638425631, 383979204, 312814129, 489869852, 508585158, 217348855, 720294691, 997637005, 678464602, 875184886, 85231775, 730651114, 440052919, 923763527, 33498836, 960768402, 235734298, 860160065, 914173703, 677979235, 409100323, 35992567, 221442883, 810221768, 298336801, 261739625, 576473075, 26213845, 195029649, 423034822, 403478835, 143612866, 720296381, 374289993, 165686059, 960787674, 566707503, 553966652, 766974401, 878177503, 624367289, 940733237, 520979700, 796039266, 908408331, 210175098, 38677421, 155046947, 47702861, 957343048, 408795358, 817974986, 269819618, 540682170, 246476495, 37762055, 73366579, 121351550, 861900525, 516612269, 882958298, 860450300, 11593608, 499794881, 710935164, 361021045, 365135632, 70668901, 119479933, 745697099, 13013101, 423322983, 994613847, 801040689, 426326389, 331146783, 757481813, 181427378, 583850852, 329556377, 353659518, 398355092, 462971720, 106319344, 332079131, 811056834, 828063466, 573286069, 647591051, 354086953, 912974443, 922866596, 215389021, 472588401, 665031927, 756002835, 838626513, 106973933, 834879327, 658145236, 411644242, 890353972, 624741660, 685968181, 13007372, 239635587, 279965295, 69030802, 549558244, 43555539, 2523024, 270850270, 845914677, 528460487, 915526267, 964757405, 72782546, 428121877, 859130626, 831799194, 931163379, 239658469, 123134912, 847021627, 982310210, 38460056, 177884826, 127722790, 729893827, 914162802, 688777204, 94576398, 507055180, 677799390, 814547910, 844670475, 536660324, 311841278, 835137530, 569524167, 250105245, 737911129, 388076113, 298968154, 505895660, 691882603, 889684466, 162779033, 500827316, 468894651, 584738962, 544285469, 68810898, 435006851, 693338358, 728888023, 999966614, 792342283, 629506139, 729476586, 766550363, 592812615, 172135045, 559453166, 889893764, 314563066, 805944257, 974089834, 180013015, 325878575, 79755506, 196783003, 642844817, 202541473, 29055869, 619713256, 828088482, 181827432, 757039571, 727233329, 503606176, 738191941, 550892121, 785667388, 656506353, 348903684, 636843320, 681758150, 772033684, 313906616, 813335790, 392714969, 697877042, 238672684, 44580922, 137804505, 605415267, 263465404, 968251952, 675787501, 722805172, 451611105, 706261458, 437319867, 500843506, 954035373, 473374716, 729466502, 118461996, 623289959, 311606969, 229811135, 215967134, 839505038, 121550241, 102576960, 646153536, 958949763, 753868689, 733958192, 193178516, 845154740, 495360324, 288038497, 224835003, 594568858, 752940606, 291851453, 635965874, 926560636, 739802671, 205372256, 906103280, 641635196, 652514068, 584856352, 378665587, 297118852, 92440715, 148745022, 414714932, 827883271, 346466696, 501059037, 436294661, 531891165, 656165311, 795375502, 201015821, 429257110, 243182310, 638246223, 271589295, 65113255, 934082436, 387806086, 606095453, 779547635, 675268483, 324793235, 725156363, 21137314, 200976528, 166878558, 820520073, 702939312, 43813678, 546942535, 691721475, 917979799, 555749305, 233088532, 569919343, 473759717, 353447949, 869632805, 368353044, 680006192, 516372682, 205588593, 414385786, 255648938, 803541731, 956469297, 118908739, 377702011, 628860704, 151798222, 855767560, 603997177, 903266061, 933795904, 547495823, 381749534, 888564976, 235972628, 635517589, 994318835, 231684615, 105839102, 583984266, 815675389, 278608688, 81402030, 197538672, 755635691, 431730410, 689875226, 977770957, 989594640, 833638881, 289622090, 338333869, 975696049, 964204622, 261471778, 565283088, 693363361, 952681284, 754590424, 392674695, 715032395, 307448670, 285883141, 897348375, 753413340, 951744591, 315819798, 107716268, 529580777, 903470907, 942609245, 489547473, 434280718, 34662022, 495430761, 634948407, 587271296, 29703081, 932302977, 551974317, 658663614, 470986097, 724528605, 920908715, 822016333, 311198613, 810724457, 479467705, 989981494, 635067325, 614712330, 988880228, 270979660, 918561425, 453225919, 623541478, 73392830, 735757681, 208323086, 182880040, 827823195, 955431880, 153174106, 698845229, 761012493, 936055514, 67358182, 413228032, 329097921, 723414688, 335256529, 721749258, 162037568, 481329163, 577278493, 93638306, 153347788, 742727496, 351147138, 871993879, 323533303, 773906648, 506322, 556521745, 287633393, 538172794, 164941247, 930084853, 756537632, 414838185, 53880491, 417557514, 212939867, 932783132, 125805914, 444840990, 231503325, 134415910, 759121957, 159732739, 473024572, 307619356, 264472778, 297618996, 487469361, 454224909, 31343916, 78659180, 650012756, 204311114, 564295188, 130616302, 93454747, 856298548, 739207813, 863541656, 997013414, 410397106, 2108023, 291042169, 228043455, 275780011, 938608374, 181289821, 773813362, 454562311, 483518397, 305306063, 509107247, 432671193, 491175991, 724231269, 126146078, 392703996, 75818381, 848699848, 752379786, 310257514, 911935926, 351841810, 657911858, 376238386, 694170688, 441067285, 764207246, 641533046, 712809407, 641437277, 273064004, 996189326, 75845337, 384715200, 732610376, 753763197, 239401839, 369899471, 119152833, 372110367, 288089291, 599832445, 163889586, 499850405, 656121043, 737072385, 461630281, 61311264, 203085620, 836046638, 350424205, 859128701, 662681652, 428544585, 122776721, 390857892, 449088279, 738901431, 2553805, 441840019, 400570074, 99234095, 21890972, 855155667, 433793088, 589731115, 477602251, 339707191, 837739474, 34856298, 90091311, 993124691, 942777182, 33094720, 355019933, 285143277, 176214329, 17362031, 529556064, 165756290, 190479760, 968576773, 116723075, 159365483, 69784937, 853743636, 869491974, 474335150, 357415910, 442052247, 434912909, 93177418, 719012418, 590171990, 529916499, 960408271, 489036238, 950629789, 454396076, 196129071, 905297363, 87943393, 883484912, 617025351, 982756274, 183052440, 779803817, 140221769, 635693513, 579002133, 651811682, 794288616, 213017901, 684737806, 597669341, 588456006, 30587178, 526957383, 920528464, 835963254, 271948285, 316208038, 620482939, 729198395, 837016387, 442669737, 580255851, 62129736, 564841051, 181267218, 221790824, 349977138, 204184591, 997460073, 927207232, 904336248, 580404331, 822849008, 225064439, 973286792, 476088289, 613211765, 992298725, 250648338, 993079651, 955573907, 176356546, 585557416, 537854631, 955561984, 721276657, 564579821, 922222165, 181146373, 759542255, 578829674, 949629356, 938304526, 530576359, 514004760, 616989162, 872148513, 351206793, 56821616, 320347959, 536887816, 198288788, 429452591, 998073125, 885609683, 346157463, 767860233, 448125893, 714698149, 313304817, 744237702, 174569803, 435187144, 242462496, 814424645, 845954664, 729397389, 348157077, 147099163, 215207948, 23195255, 990486680, 586536754, 906265121, 923297948, 459752639, 63635044, 413993261, 552060442, 672650098, 449751376, 584362903, 100399270, 933197506, 627556479, 378362095, 138717825, 78043005, 133641473, 183521438, 336882564, 928315745, 958202574, 643554692 };


int main() {
	/*
	MI c = 1;
	inc(i, 500'000'001) {
		if(i % 500'000 == 0) {
			cout << c << ", ";
		}
		
		MI m = i;
		c *= (2 * m + 1) * (2 * m + 2) / ((m + 1) * (m + 1));
	}
	*/
	
	const int B = 500'000;
	
	LL k;
	cin >> k;
	
	MI ans;
	if(k % 2 == 0) {
		k /= 2;
		
		ans = a[k / B];
		inc(i, k % B) {
			MI m = k / B * B + i;
			ans *= (2 * m + 1) * (2 * m + 2) / ((m + 1) * (m + 1));
		}
	} else { ans = 0; }
	
	cout << ans << endl;
	
	return 0;
}

yukicoder

結果

テストケース

ソースコード