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

提出ソース

結果

問題	No.502 階乗を計算するだけ
ユーザー	siro53
提出日時	2020-09-15 01:16:38
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	9 ms / 1,000 ms
コード長	15,484 bytes
コンパイル時間	4,256 ms
コンパイル使用メモリ	276,056 KB
実行使用メモリ	4,384 KB
最終ジャッジ日時	2023-09-04 00:55:45
合計ジャッジ時間	5,375 ms
ジャッジサーバーID （参考情報）	judge14 / judge13

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,380 KB
testcase_01	AC	2 ms 4,380 KB
testcase_02	AC	2 ms 4,380 KB
testcase_03	AC	2 ms 4,380 KB
testcase_04	AC	2 ms 4,380 KB
testcase_05	AC	2 ms 4,376 KB
testcase_06	AC	2 ms 4,376 KB
testcase_07	AC	1 ms 4,380 KB
testcase_08	AC	2 ms 4,380 KB
testcase_09	AC	1 ms 4,376 KB
testcase_10	AC	1 ms 4,376 KB
testcase_11	AC	2 ms 4,376 KB
testcase_12	AC	1 ms 4,384 KB
testcase_13	AC	2 ms 4,376 KB
testcase_14	AC	2 ms 4,376 KB
testcase_15	AC	2 ms 4,376 KB
testcase_16	AC	1 ms 4,376 KB
testcase_17	AC	2 ms 4,380 KB
testcase_18	AC	2 ms 4,380 KB
testcase_19	AC	1 ms 4,376 KB
testcase_20	AC	1 ms 4,380 KB
testcase_21	AC	1 ms 4,376 KB
testcase_22	AC	7 ms 4,384 KB
testcase_23	AC	3 ms 4,380 KB
testcase_24	AC	5 ms 4,380 KB
testcase_25	AC	3 ms 4,380 KB
testcase_26	AC	4 ms 4,380 KB
testcase_27	AC	3 ms 4,380 KB
testcase_28	AC	4 ms 4,380 KB
testcase_29	AC	3 ms 4,380 KB
testcase_30	AC	7 ms 4,376 KB
testcase_31	AC	4 ms 4,380 KB
testcase_32	AC	2 ms 4,380 KB
testcase_33	AC	9 ms 4,380 KB
testcase_34	AC	4 ms 4,380 KB
testcase_35	AC	7 ms 4,380 KB
testcase_36	AC	3 ms 4,384 KB
testcase_37	AC	7 ms 4,376 KB
testcase_38	AC	3 ms 4,380 KB
testcase_39	AC	6 ms 4,380 KB
testcase_40	AC	5 ms 4,380 KB
testcase_41	AC	2 ms 4,384 KB
testcase_42	AC	2 ms 4,376 KB
testcase_43	AC	1 ms 4,384 KB
testcase_44	AC	1 ms 4,376 KB
testcase_45	AC	2 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	2 ms 4,376 KB
testcase_50	AC	2 ms 4,380 KB
testcase_51	AC	1 ms 4,380 KB

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

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;
template <class T> inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T> inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return 1;
    }
    return 0;
}
#define DEBUG
#ifdef DEBUG
template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
    os << '(' << p.first << ',' << p.second << ')';
    return os;
}
template <class T> ostream &operator<<(ostream &os, const vector<T> &v) {
    os << '{';
    for(int i = 0; i < (int)v.size(); i++) {
        if(i) {
            os << ',';
        }
        os << v[i];
    }
    os << '}';
    return os;
}
void debugg() { cerr << endl; }
template <class T, class... Args>
void debugg(const T &x, const Args &... args) {
    cerr << " " << x;
    debugg(args...);
}
#define debug(...)                                                             \
    cerr << __LINE__ << " [" << #__VA_ARGS__ << "]:", debugg(__VA_ARGS__)
#define dump(x) cerr << __LINE__ << " " << #x << " = " << (x) << endl
#else
#define debug(...) (void(0))
#define dump(x) (void(0))
#endif

struct Setup {
    Setup() {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(15);
    }
} __Setup;

using ll = long long;
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
const double EPS = 1e-7;
const int INF = 1 << 30;
const ll LLINF = 1LL << 60;
constexpr int MOD = 1000000007;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

//-------------------------------------

template <int mod> struct ModInt {
    int x;

    ModInt() : x(0) {}

    ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}

    ModInt &operator+=(const ModInt &p) {
        if((x += p.x) >= mod)
            x -= mod;
        return *this;
    }

    ModInt &operator-=(const ModInt &p) {
        if((x += mod - p.x) >= mod)
            x -= mod;
        return *this;
    }

    ModInt &operator*=(const ModInt &p) {
        x = (int)(1LL * x * p.x % mod);
        return *this;
    }

    ModInt &operator/=(const ModInt &p) {
        *this *= p.inverse();
        return *this;
    }

    ModInt operator-() const { return ModInt(-x); }

    ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }

    ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }

    ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }

    ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }

    bool operator==(const ModInt &p) const { return x == p.x; }

    bool operator!=(const ModInt &p) const { return x != p.x; }

    ModInt inverse() const {
        int a = x, b = mod, u = 1, v = 0, t;
        while(b > 0) {
            t = a / b;
            swap(a -= t * b, b);
            swap(u -= t * v, v);
        }
        return ModInt(u);
    }

    ModInt pow(int64_t n) const {
        ModInt ret(1), mul(x);
        while(n > 0) {
            if(n & 1)
                ret *= mul;
            mul *= mul;
            n >>= 1;
        }
        return ret;
    }

    friend ostream &operator<<(ostream &os, const ModInt &p) {
        return os << p.x;
    }

    friend istream &operator>>(istream &is, ModInt &a) {
        int64_t t;
        is >> t;
        a = ModInt<mod>(t);
        return (is);
    }

    static int get_mod() { return mod; }
};

using mint = ModInt<MOD>;

const vector<mint> pre = {
    1,         41102369,  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, 876297919,
    934814019, 676405347, 567277637, 112249297, 44930135,  39417871,
    47401357,  108819476, 281863274, 60168088,  692636218, 432775082,
    14235602,  770511792, 400295761, 697066277, 421835306, 220108638,
    661224977, 261799937, 168203998, 802214249, 544064410, 935080803,
    583967898, 211768084, 751231582, 972424306, 623534362, 335160196,
    243276029, 554749550, 60050552,  797848181, 395891998, 172428290,
    159554990, 887420150, 970055531, 250388809, 487998999, 856259313,
    82104855,  232253360, 513365505, 244109365, 1559745,   695345956,
    261384175, 849009131, 323214113, 747664143, 444090941, 659224434,
    80729842,  570033864, 664989237, 827348878, 195888993, 576798521,
    457882808, 731551699, 212938473, 509096183, 827544702, 678320208,
    677711203, 289752035, 66404266,  555972231, 195290384, 97136305,
    349551356, 785113347, 83489485,  66247239,  52167191,  307390891,
    547665832, 143066173, 350016754, 917404120, 296269301, 996122673,
    23015220,  602139210, 748566338, 187348575, 109838563, 574053420,
    105574531, 304173654, 542432219, 34538816,  325636655, 437843114,
    630621321, 26853683,  933245637, 616368450, 238971581, 511371690,
    557301633, 911398531, 848952161, 958992544, 925152039, 914456118,
    724691727, 636817583, 238087006, 946237212, 910291942, 114985663,
    492237273, 450387329, 834860913, 763017204, 368925948, 475812562,
    740594930, 45060610,  806047532, 464456846, 172115341, 75307702,
    116261993, 562519302, 268838846, 173784895, 243624360, 61570384,
    481661251, 938269070, 95182730,  91068149,  115435332, 495022305,
    136026497, 506496856, 710729672, 113570024, 366384665, 564758715,
    270239666, 277118392, 79874094,  702807165, 112390913, 730341625,
    103056890, 677948390, 339464594, 167240465, 108312174, 839079953,
    479334442, 271788964, 135498044, 277717575, 591048681, 811637561,
    353339603, 889410460, 839849206, 192345193, 736265527, 316439118,
    217544623, 788132977, 618898635, 183011467, 380858207, 996097969,
    898554793, 335353644, 54062950,  611251733, 419363534, 965429853,
    160398980, 151319402, 990918946, 607730875, 450718279, 173539388,
    648991369, 970937898, 500780548, 780122909, 39052406,  276894233,
    460373282, 651081062, 461415770, 358700839, 643638805, 560006119,
    668123525, 686692315, 673464765, 957633609, 199866123, 563432246,
    841799766, 385330357, 504962686, 954061253, 128487469, 685707545,
    299172297, 717975101, 577786541, 318951960, 773206631, 306832604,
    204355779, 573592106, 30977140,  450398100, 363172638, 258379324,
    472935553, 93940075,  587220627, 776264326, 793270300, 291733496,
    522049725, 579995261, 335416359, 142946099, 472012302, 559947225,
    332139472, 499377092, 464599136, 164752359, 309058615, 86117128,
    580204973, 563781682, 954840109, 624577416, 895609896, 888287558,
    836813268, 926036911, 386027524, 184419613, 724205533, 403351886,
    715247054, 716986954, 830567832, 383388563, 68409439,  6734065,
    189239124, 68322490,  943653305, 405755338, 811056092, 179518046,
    825132993, 343807435, 985084650, 868553027, 148528617, 160684257,
    882148737, 591915968, 701445829, 529726489, 302177126, 974886682,
    241107368, 798830099, 940567523, 11633075,  325334066, 346091869,
    115312728, 473718967, 218129285, 878471898, 180002392, 699739374,
    917084264, 856859395, 435327356, 808651347, 421623838, 105419548,
    59883031,  322487421, 79716267,  715317963, 429277690, 398078032,
    316486674, 384843585, 940338439, 937409008, 940524812, 947549662,
    833550543, 593524514, 996164327, 987314628, 697611981, 636177449,
    274192146, 418537348, 925347821, 952831975, 893732627, 1277567,
    358655417, 141866945, 581830879, 987597705, 347046911, 775305697,
    125354499, 951540811, 247662371, 343043237, 568392357, 997474832,
    209244402, 380480118, 149586983, 392838702, 309134554, 990779998,
    263053337, 325362513, 780072518, 551028176, 990826116, 989944961,
    155569943, 596737944, 711553356, 268844715, 451373308, 379404150,
    462639908, 961812918, 654611901, 382776490, 41815820,  843321396,
    675258797, 845583555, 934281721, 741114145, 275105629, 666247477,
    325912072, 526131620, 252551589, 432030917, 554917439, 818036959,
    754363835, 795190182, 909210595, 278704903, 719566487, 628514947,
    424989675, 321685608, 50590510,  832069712, 198768464, 702004730,
    99199382,  707469729, 747407118, 302020341, 497196934, 5003231,
    726997875, 382617671, 296229203, 183888367, 703397904, 552133875,
    732868367, 350095207, 26031303,  863250534, 216665960, 561745549,
    352946234, 784139777, 733333339, 503105966, 459878625, 803187381,
    16634739,  180898306, 68718097,  985594252, 404206040, 749724532,
    97830135,  611751357, 31131935,  662741752, 864326453, 864869025,
    167831173, 559214642, 718498895, 91352335,  608823837, 473379392,
    385388084, 152267158, 681756977, 46819124,  313132653, 56547945,
    442795120, 796616594, 256141983, 152028387, 636578562, 385377759,
    553033642, 491415383, 919273670, 996049638, 326686486, 160150665,
    141827977, 540818053, 693305776, 593938674, 186576440, 688809790,
    565456578, 749296077, 519397500, 551096742, 696628828, 775025061,
    370732451, 164246193, 915265013, 457469634, 923043932, 912368644,
    777901604, 464118005, 637939935, 956856710, 490676632, 453019482,
    462528877, 502297454, 798895521, 100498586, 699767918, 849974789,
    811575797, 438952959, 606870929, 907720182, 179111720, 48053248,
    508038818, 811944661, 752550134, 401382061, 848924691, 764368449,
    34629406,  529840945, 435904287, 26011548,  208184231, 446477394,
    206330671, 366033520, 131772368, 185646898, 648711554, 472759660,
    523696723, 271198437, 25058942,  859369491, 817928963, 330711333,
    724464507, 437605233, 701453022, 626663115, 281230685, 510650790,
    596949867, 295726547, 303076380, 465070856, 272814771, 538771609,
    48824684,  951279549, 939889684, 564188856, 48527183,  201307702,
    484458461, 861754542, 326159309, 181594759, 668422905, 286273596,
    965656187, 44135644,  359960756, 936229527, 407934361, 267193060,
    456152084, 459116722, 124804049, 262322489, 920251227, 816929577,
    483924582, 151834896, 167087470, 490222511, 903466878, 361583925,
    368114731, 339383292, 388728584, 218107212, 249153339, 909458706,
    322908524, 202649964, 92255682,  573074791, 15570863,  94331513,
    744158074, 196345098, 334326205, 9416035,   98349682,  882121662,
    769795511, 231988936, 888146074, 137603545, 582627184, 407518072,
    919419361, 909433461, 986708498, 310317874, 373745190, 263645931,
    256853930, 876379959, 702823274, 147050765, 308186532, 175504139,
    180350107, 797736554, 606241871, 384547635, 273712630, 586444655,
    682189174, 666493603, 946867127, 819114541, 502371023, 261970285,
    825871994, 126925175, 701506133, 314738056, 341779962, 561011609,
    815463367, 46765164,  49187570,  188054995, 957939114, 64814326,
    933376898, 329837066, 338121343, 765215899, 869630152, 978119194,
    632627667, 975266085, 435887178, 282092463, 129621197, 758245605,
    827722926, 201339230, 918513230, 322096036, 547838438, 985546115,
    852304035, 593090119, 689189630, 555842733, 567033437, 469928208,
    212842957, 117842065, 404149413, 155133422, 663307737, 208761293,
    206282795, 717946122, 488906585, 414236650, 280700600, 962670136,
    534279149, 214569244, 375297772, 811053196, 922377372, 289594327,
    219932130, 211487466, 701050258, 398782410, 863002719, 27236531,
    217598709, 375472836, 810551911, 178598958, 247844667, 676526196,
    812283640, 863066876, 857241854, 113917835, 624148346, 726089763,
    564827277, 826300950, 478982047, 439411911, 454039189, 633292726,
    48562889,  802100365, 671734977, 945204804, 508831870, 398781902,
    897162044, 644050694, 892168027, 828883117, 277714559, 713448377,
    624500515, 590098114, 808691930, 514359662, 895205045, 715264908,
    628829100, 484492064, 919717789, 513196123, 748510389, 403652653,
    574455974, 77123823,  172096141, 819801784, 581418893, 15655126,
    15391652,  875641535, 203191898, 264582598, 880691101, 907800444,
    986598821, 340030191, 264688936, 369832433, 785804644, 842065079,
    423951674, 663560047, 696623384, 496709826, 161960209, 331910086,
    541120825, 951524114, 841656666, 162683802, 629786193, 190395535,
    269571439, 832671304, 76770272,  341080135, 421943723, 494210290,
    751040886, 317076664, 672850561, 72482816,  493689107, 135625240,
    100228913, 684748812, 639655136, 906233141, 929893103, 277813439,
    814362881, 562608724, 406024012, 885537778, 10065330,  60625018,
    983737173, 60517502,  551060742, 804930491, 823845496, 727416538,
    946421040, 678171399, 842203531, 175638827, 894247956, 538609927,
    885362182, 946464959, 116667533, 749816133, 241427979, 871117927,
    281804989, 163928347, 563796647, 640266394, 774625892, 59342705,
    256473217, 674115061, 918860977, 322633051, 753513874, 393556719,
    304644842, 767372800, 161362528, 754787150, 627655552, 677395736,
    799289297, 846650652, 816701166, 687265514, 787113234, 358757251,
    701220427, 607715125, 245795606, 600624983, 10475577,  728620948,
    759404319, 36292292,  491466901, 22556579,  114495791, 647630109,
    586445753, 482254337, 718623833, 763514207, 66547751,  953634340,
    351472920, 308474522, 494166907, 634359666, 172114298, 865440961,
    364380585, 921648059, 965683742, 260466949, 117483873, 962540888,
    237120480, 620531822, 193781724, 213092254, 107141741, 602742426,
    793307102, 756154604, 236455213, 362928234, 14162538,  753042874,
    778983779, 25977209,  49389215,  698308420, 859637374, 49031023,
    713258160, 737331920, 923333660, 804861409, 83868974,  682873215,
    217298111, 883278906, 176966527, 954913,    105359006, 390019735,
    10430738,  706334445, 315103615, 567473423, 708233401, 48160594,
    946149627, 346966053, 281329488, 462880311, 31503476,  185438078,
    965785236, 992656683, 916291845, 881482632, 899946391, 321900901,
    512634493, 303338827, 121000338, 967284733, 492741665, 152233223,
    165393390, 680128316, 917041303, 532702135, 741626808, 496442755,
    536841269, 131384366, 377329025, 301196854, 859917803, 676511002,
    373451745, 847645126, 823495900, 576368335, 73146164,  954958912,
    847549272, 241289571, 646654592, 216046746, 205951465, 3258987,
    780882948, 822439091, 598245292, 869544707, 698611116};

constexpr int B = 1000000;

int main() {
    ll n;
    cin >> n;
    if(n >= MOD) {
        cout << 0 << endl;
        return 0;
    }
    int id = n / B;
    int base = B * id;
    mint ans = pre[id];
    for(int i = 1; i <= n - B * id; i++) {
        ans *= mint(base + i);
    }
    cout << ans << endl;
}

yukicoder

結果

テストケース

ソースコード