結果

問題 No.2747 Permutation Adjacent Sum
ユーザー Series_205Series_205
提出日時 2024-04-20 14:41:44
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2,034 ms / 3,000 ms
コード長 14,740 bytes
コンパイル時間 1,956 ms
コンパイル使用メモリ 196,784 KB
実行使用メモリ 19,212 KB
最終ジャッジ日時 2024-04-20 14:42:29
合計ジャッジ時間 40,064 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 731 ms
10,836 KB
testcase_01 AC 68 ms
6,944 KB
testcase_02 AC 479 ms
9,748 KB
testcase_03 AC 62 ms
6,940 KB
testcase_04 AC 833 ms
12,052 KB
testcase_05 AC 2,017 ms
19,036 KB
testcase_06 AC 887 ms
12,536 KB
testcase_07 AC 731 ms
11,876 KB
testcase_08 AC 1,233 ms
13,964 KB
testcase_09 AC 1,728 ms
17,236 KB
testcase_10 AC 197 ms
6,940 KB
testcase_11 AC 742 ms
10,160 KB
testcase_12 AC 6 ms
6,940 KB
testcase_13 AC 311 ms
6,940 KB
testcase_14 AC 1,104 ms
14,600 KB
testcase_15 AC 1,699 ms
16,580 KB
testcase_16 AC 798 ms
11,644 KB
testcase_17 AC 1,583 ms
16,168 KB
testcase_18 AC 1,483 ms
17,012 KB
testcase_19 AC 122 ms
6,940 KB
testcase_20 AC 789 ms
12,316 KB
testcase_21 AC 1,255 ms
15,188 KB
testcase_22 AC 1,403 ms
15,992 KB
testcase_23 AC 602 ms
8,636 KB
testcase_24 AC 651 ms
12,072 KB
testcase_25 AC 461 ms
9,636 KB
testcase_26 AC 1,092 ms
15,324 KB
testcase_27 AC 1,278 ms
15,028 KB
testcase_28 AC 1,185 ms
13,516 KB
testcase_29 AC 824 ms
12,252 KB
testcase_30 AC 1,998 ms
19,052 KB
testcase_31 AC 2,029 ms
19,168 KB
testcase_32 AC 1,999 ms
19,100 KB
testcase_33 AC 2,034 ms
19,212 KB
testcase_34 AC 1,959 ms
19,168 KB
testcase_35 AC 2 ms
6,940 KB
testcase_36 AC 2 ms
6,944 KB
testcase_37 AC 2 ms
6,940 KB
testcase_38 AC 1 ms
6,940 KB
testcase_39 AC 1 ms
6,940 KB
testcase_40 AC 1 ms
6,940 KB
testcase_41 AC 1 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define FOR(i, l, r) for(ll i = l; i < r; i++)
#define rep(i, n) FOR(i, 0, n)
#define FORR(i, l, r) for(ll i = r - 1; i >= l; i--)
#define ALL(ar) begin(ar), end(ar)

template <typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) {
    return a < b && (a = b, true);
}
template <typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) {
    return a > b && (a = b, true);
}
template <typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) {
    is >> p.first >> p.second;
    return is;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
    os << p.first << ' ' << p.second;
    return os;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &v) {
    for(T &x : v) is >> x;
    return is;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    for(size_t i = 0; i < v.size(); i++) os << (i ? " " : "") << v[i];
    return os;
}
//-------------------------------------------------
template <typename T>
T floor(T a, T b) {
    return a / b - (a % b && (a ^ b) < 0);
}
template <typename T>
pair<T, T> divmod(T x, T y) {
    T q = floor(x, y);
    return {q, x - q * y};
}

int factorial998table[1024] = {
    1,         467742124, 703158536, 849331177, 183632821, 786787592, 708945888,
    623860151, 442444797, 339076928, 916211838, 827641482, 982515753, 303461550,
    466748179, 669060208, 789885751, 915736046, 189957301, 934038903, 728735046,
    774755699, 649374308, 602288735, 492352484, 958678776, 943233257, 148504501,
    352124178, 569334038, 927469492, 343841688, 432351202, 700916755, 170721982,
    8283809,   875807278, 931632987, 330722936, 603566523, 391470976, 157944106,
    826756015, 278928878, 178606531, 522053153, 175494307, 16217485,  310769109,
    430912024, 970167731, 302127847, 960178710, 607169580, 211863227, 918097328,
    664502958, 598427325, 415194799, 38321157,  375608821, 557298612, 497769749,
    114695383, 77784134,  629192790, 339438380, 348348875, 713806860, 526342541,
    671850855, 414726935, 844082152, 412454739, 351143550, 868784407, 834684152,
    186057224, 996072584, 619190001, 24770542,  765280770, 513490122, 468949120,
    867194196, 866447292, 937135640, 560788103, 308335177, 703539315, 252044620,
    119916775, 298069903, 43651994,  148641017, 730387621, 856452172, 74265901,
    626807500, 980602375, 42825068,  348086475, 162321900, 207340584, 151258454,
    461547160, 320321845, 361026143, 882876292, 842563318, 257705870, 158156446,
    292795459, 984763947, 917068833, 811332379, 782439665, 944504775, 298167161,
    141501910, 155584237, 149720256, 71954352,  666430555, 580966229, 884747116,
    616367471, 918981127, 310328833, 724405658, 383796145, 256700166, 487819118,
    642491144, 181867555, 524937737, 222137750, 445244561, 79921588,  253457448,
    405659726, 260707689, 740044210, 654653354, 229885020, 230551611, 616689587,
    939003921, 565960348, 904184966, 133298693, 859220865, 186139683, 765071679,
    247651638, 451157944, 929341123, 503724944, 768266737, 142218056, 910573117,
    274579400, 151387843, 212671109, 815271666, 406331931, 154251304, 642676789,
    570372925, 976277122, 442985463, 928799971, 817581666, 797627351, 100113334,
    877639265, 541537097, 434482347, 300960222, 270085755, 481153328, 236088097,
    686884498, 323505794, 897572220, 900787550, 277507290, 157634146, 892066519,
    616420589, 46056764,  697140618, 592483685, 896871487, 896388868, 106444279,
    115102765, 191484323, 62322499,  434613622, 426026852, 378184205, 194359325,
    415197585, 965735328, 598860936, 653751428, 942602959, 475099103, 642401460,
    77868208,  464952529, 549976420, 705774928, 635299526, 704085554, 809044086,
    670938184, 799176916, 58985566,  402328281, 182103192, 921913660, 674272214,
    428301920, 520916749, 127424638, 296779896, 166780239, 19634060,  95873539,
    708947606, 532272305, 980167862, 7015847,   370183454, 45567119,  866949818,
    374428494, 25583689,  351370758, 835388325, 232690098, 42002598,  17055285,
    985022727, 214528454, 122907290, 793349516, 609331634, 87133548,  248246624,
    448572380, 502875867, 183097664, 536117329, 170926160, 381772251, 37038194,
    374439881, 94285547,  880631489, 452052533, 739811514, 675382782, 587926712,
    179133902, 694266603, 338843576, 281485671, 813341519, 616512705, 222785194,
    382494725, 471654428, 961907947, 442140830, 702296161, 548575377, 388901073,
    19119024,  545916498, 947169254, 801677200, 377657430, 634980290, 246239186,
    13175103,  239754689, 656729178, 364003283, 646568868, 584909084, 690387116,
    452007054, 131381944, 908149670, 807287523, 802277179, 745423153, 893994782,
    197548253, 376096720, 105840336, 687751559, 170787791, 928507410, 620382696,
    446955151, 139665212, 882526402, 494793004, 107171423, 753993075, 467588754,
    207595897, 269813018, 941027990, 856873596, 717085190, 245280646, 792026805,
    548741735, 523767341, 637697735, 261200153, 89666563,  344573088, 15832984,
    558492246, 825051585, 923222974, 826620400, 558080789, 657328927, 991078225,
    706029275, 738905108, 401212366, 980043233, 895405022, 597894231, 636951913,
    947342478, 786075225, 395095090, 188433847, 121279219, 860403973, 396099425,
    240442489, 521535558, 280382318, 58023116,  735594008, 8696133,   477645338,
    223630480, 816606673, 680021043, 362424474, 181667447, 504295826, 332167472,
    766361494, 992840497, 417671938, 376941230, 11880047,  275790726, 106186450,
    150546053, 966438917, 431896075, 158021876, 734833661, 328332504, 632143386,
    962477966, 638741189, 728804571, 753715698, 20536106,  45105841,  271673172,
    982138522, 604809222, 199722980, 211807634, 478008419, 194715230, 246865373,
    316443541, 869035744, 202922168, 245262975, 136244583, 650969410, 566222746,
    55188168,  495968583, 571946805, 188658038, 353720239, 830419870, 669127165,
    86710835,  810103736, 630008035, 764354348, 209246227, 277861984, 725469211,
    151404581, 894191013, 775554083, 634671016, 170299187, 471849450, 575347258,
    505276194, 636730506, 40086858,  386228700, 789875034, 998219457, 359035788,
    843760715, 864829665, 794240359, 241486050, 48334220,  583177582, 714653706,
    617669563, 132782021, 779225352, 333301287, 520569296, 508276228, 689073648,
    573645847, 200419842, 911561316, 310562870, 204959007, 879280837, 762843188,
    103128368, 133300147, 648946778, 287218789, 662474952, 587555465, 105622721,
    648151526, 517033362, 729251452, 850555187, 708613432, 874408867, 345608416,
    690718720, 10813958,  42384375,  882264058, 825490058, 252850511, 652942840,
    202604098, 277615259, 862885671, 582470925, 190843016, 534488148, 187675153,
    911660635, 377262012, 642854978, 359397276, 712333871, 580131409, 841639861,
    925383257, 213683380, 25291651,  974815450, 32032244,  119030165, 443676106,
    555727293, 170519648, 171131074, 839941962, 789829593, 140975543, 845347712,
    303299112, 530420097, 857005350, 249174130, 224087061, 311280308, 404814306,
    567648772, 766512373, 470895965, 294358155, 625218604, 89534510,  513216330,
    78173719,  22818060,  254922573, 292417477, 415060121, 208989124, 960117615,
    570018845, 237661008, 442774488, 871349246, 161574942, 548661451, 313471555,
    448096394, 587422360, 987939533, 254478574, 113844945, 268886375, 927289435,
    664834607, 983476167, 390569280, 363763327, 935767957, 159015901, 508613041,
    134148582, 127417680, 484767855, 825835285, 43847241,  972918293, 151969014,
    768480291, 729490470, 76727400,  384998943, 648970509, 764966281, 391326774,
    585299643, 661473977, 530021579, 368308424, 81083443,  981417794, 185781362,
    169555925, 934957641, 56005264,  296483160, 853982963, 489694611, 73207251,
    20297311,  431253211, 168162850, 36271383,  689526671, 397669110, 705876730,
    785504919, 764896820, 936514026, 350141918, 784778738, 682324919, 140913543,
    862125900, 723248565, 369074340, 146936534, 226913694, 277886748, 856792647,
    13654547,  141461269, 255233971, 979535193, 747662027, 452683681, 338311679,
    399620140, 306913085, 817524367, 333578440, 943193170, 387930488, 964713035,
    554372227, 524201507, 267870305, 698863503, 695139108, 399857384, 830659092,
    479624682, 594238820, 768224890, 956955770, 940576967, 920740072, 282055556,
    621677930, 847367415, 619094041, 432519599, 192780811, 912052381, 263304046,
    114280963, 307107320, 956809356, 118706101, 836710721, 356893069, 427113038,
    55360495,  892694364, 443807400, 568616581, 130165565, 732273554, 778059496,
    95936679,  629634134, 383940143, 474733431, 271200931, 253893765, 65679204,
    670721645, 268831988, 225698685, 424701963, 654858732, 405695790, 894299102,
    797306377, 464723449, 647679843, 730366154, 956550665, 898568348, 313188681,
    661403769, 346715295, 358990430, 868898456, 719464962, 978551995, 772931269,
    255694712, 379904456, 393101377, 130818973, 810783770, 78951115,  608848341,
    941552927, 523163696, 581658405, 188869913, 161971620, 114600913, 300038465,
    126906968, 572973411, 118017645, 806069307, 430432761, 310699012, 989119052,
    282768145, 557792692, 611036992, 427168405, 84497995,  529589599, 967936672,
    416953197, 549641787, 787274930, 514952744, 646568513, 39329263,  765390776,
    831388678, 299074396, 102522509, 886062498, 598990751, 553048069, 305737423,
    388746841, 13007805,  3445560,   568306294, 109543305, 847740132, 746222360,
    454654676, 748993028, 222910140, 861308982, 390243513, 692742883, 789475199,
    153430402, 299806798, 913070840, 881332402, 245792511, 618823409, 1817990,
    897836424, 726794141, 700802042, 472214481, 97004031,  479899815, 573979309,
    752576644, 374801082, 599964908, 894966385, 178103304, 12240556,  393873628,
    855241924, 305678131, 971858774, 281586141, 87362107,  41844894,  175133514,
    276243521, 997376957, 260427125, 439339251, 64661516,  362212695, 186181824,
    423316311, 267640938, 299252572, 810040987, 857956827, 758991665, 207700847,
    399398818, 747579039, 814755712, 298373935, 307448236, 42074518,  982127624,
    538863790, 528558929, 96501138,  813255509, 611769398, 710541518, 408153968,
    675346745, 970094012, 791931126, 811516976, 618049736, 264048084, 209805699,
    909045292, 645349311, 416989597, 590393407, 320547207, 342653696, 860169617,
    856611053, 475149267, 124801433, 547187333, 466598598, 266454901, 554467907,
    868909135, 199244107, 548833449, 20952517,  234169026, 117025205, 804238552,
    205574540, 590283297, 822322644, 866010856, 477388420, 935768507, 424373916,
    951967787, 344871828, 133969287, 937034425, 309380768, 666909962, 726492795,
    996576193, 883938945, 869749688, 313581344, 65216237,  88860786,  208895640,
    888760811, 854567609, 328142793, 121852766, 928690075, 135269006, 333105486,
    502240551, 573712984, 397698082, 935117672, 718828733, 440474396, 335628894,
    184935718, 788258676, 646732201, 68099895,  167036421, 362572358, 787671392,
    666366534, 193503119, 74429287,  132805884, 796935846, 124574194, 926012440,
    147265585, 722608579, 526866610, 452261307, 990444071, 4595579,   147427028,
    774597449, 678783012, 568563934, 383628463, 68242206,  163493293, 352851801,
    123192034, 529859554, 14733470,  565063217, 178575398, 580871309, 135817500,
    313966456, 647215844, 118781836, 106243172, 796669460, 48496927,  772979683,
    715961917, 546863206, 601711799, 644312478, 629259662, 738295002, 692301787,
    149995411, 864799423, 284186171, 246177326, 268779154, 86400350,  518698490,
    321709079, 946212693, 800553099, 865864136, 244789848, 386206318, 851633075,
    713794602, 131117952, 280474884, 243820970, 820033654, 399700655, 825581574,
    443639603, 774376660, 362476217, 552383080, 436759518, 538430048, 965968656,
    150434699, 563163603, 352073025, 840124972, 152029247, 902082055, 770264937,
    747653807, 934664232, 541451013, 807031739, 854866728, 503502641, 283479207,
    297947602, 488469464, 205196166, 381583984, 108455782, 570592132, 363674728,
    134077711, 356931610, 887112858, 273780969, 443297964, 650953636, 402662299,
    894089640, 71844431,  33030748,  208583995, 597099208, 671156881, 875032178,
    998244352, 0,         0,         0,         0,         0,         0,
    0,         0,         0,         0,         0,         0,         0,
    0,         0,         0,         0,         0,         0,         0,
    0,         0,         0,         0,         0,         0,         0,
    0,         0,         0,         0,         0,         0,         0,
    0,         0,         0,         0,         0,         0,         0,
    0,         0,         0,         0,         0,         0,         0,
    0,         0,         0,         0,         0,         0,         0,
    0,         0,         0,         0,         0,         0,         0,
    0,         0,         0,         0,         0,         0,         0,
    0,         0};

int factorial998(ll n) {
    constexpr int mod = 998244353;
    if(n >= mod) return 0;
    auto [q, r] = divmod<int>(n, 1 << 20);
    ll x = factorial998table[q];
    int s = q << 20;
    rep(i, r) x = x * (s + i + 1) % mod;
    return x;
}

ll mo = 998244353;
ll P[1010101];
ll fact[1010101];

inline int mulmod(int a, int b, int mo) {
    int d, r;
    if(a == 0 || b == 0) return 0;
    if(a == 1 || b == 1) return max(a, b);
    __asm__(
        "mull %4;"
        "divl %2"
        : "=d"(r), "=a"(d)
        : "r"(mo), "a"(a), "d"(b));
    return r;
}

int modpow(int a, int n = mo - 2) {
    int r = 1;
    while(n) r = mulmod(r, (n % 2) ? a : 1, mo), a = mulmod(a, a, mo), n >>= 1;
    return r;
}

ll solve_(ll N, ll K) {
    int i, j, k, l, r, x, y;
    string s;

    // cin >> N >> K;

    fact[0] = 1;
    for(i = 1; i <= K + 1; i++) {
        (P[i] = modpow(i, K) + P[i - 1]) %= mo;
        fact[i] = fact[i - 1] * i % mo;
    }

    if(N <= K + 1) return P[N];
    N = N % mo + mo;

    ll ret = 0;
    ll A = 1;
    for(i = 0; i <= K + 1; i++) A = A * (N - i) % mo;

    for(i = 0; i <= K + 1; i++) {
        ll v = P[i] * A % mo * modpow(N - i) % mo;
        ll w = fact[K + 1 - i] * fact[i] % mo;
        v = v * modpow(w) % mo;

        if(i % 2 != (K + 1) % 2)
            ret = (ret + mo - v) % mo;
        else
            ret = (ret + v) % mo;
    }

    // cout << ret << endl;
    return ret;
}

void solve() {
    ll n, k;
    cin >> n >> k;

    ll a = solve_(n, k) * n % mo - solve_(n, k + 1) % mo;
    a += mo;
    a %= mo;

    a = a * 2 * factorial998(n - 1) % mo;

    cout << a << endl;
}

int main() {
    int t = 1;
    // cin >> t;
    while(t--) solve();
}
0