結果
| 問題 | No.2747 Permutation Adjacent Sum |
| ユーザー |
 Series_205
|
| 提出日時 | 2024-04-20 14:41:26 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 2,314 ms / 3,000 ms |
| コード長 | 14,832 bytes |
| コンパイル時間 | 3,418 ms |
| コンパイル使用メモリ | 220,596 KB |
| 実行使用メモリ | 19,032 KB |
| 最終ジャッジ日時 | 2024-10-12 10:18:17 |
| 合計ジャッジ時間 | 45,091 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 819 ms
10,580 KB |
| testcase_01 | AC | 67 ms
6,816 KB |
| testcase_02 | AC | 523 ms
8,128 KB |
| testcase_03 | AC | 69 ms
6,820 KB |
| testcase_04 | AC | 892 ms
11,784 KB |
| testcase_05 | AC | 2,208 ms
18,736 KB |
| testcase_06 | AC | 968 ms
11,912 KB |
| testcase_07 | AC | 783 ms
9,908 KB |
| testcase_08 | AC | 1,348 ms
16,040 KB |
| testcase_09 | AC | 1,901 ms
16,940 KB |
| testcase_10 | AC | 222 ms
6,816 KB |
| testcase_11 | AC | 799 ms
12,148 KB |
| testcase_12 | AC | 6 ms
6,820 KB |
| testcase_13 | AC | 353 ms
6,820 KB |
| testcase_14 | AC | 1,216 ms
13,956 KB |
| testcase_15 | AC | 1,856 ms
17,252 KB |
| testcase_16 | AC | 847 ms
10,512 KB |
| testcase_17 | AC | 1,710 ms
17,300 KB |
| testcase_18 | AC | 1,636 ms
15,836 KB |
| testcase_19 | AC | 140 ms
6,820 KB |
| testcase_20 | AC | 882 ms
11,424 KB |
| testcase_21 | AC | 1,366 ms
14,672 KB |
| testcase_22 | AC | 1,477 ms
15,628 KB |
| testcase_23 | AC | 673 ms
11,072 KB |
| testcase_24 | AC | 722 ms
10,580 KB |
| testcase_25 | AC | 472 ms
8,736 KB |
| testcase_26 | AC | 1,231 ms
13,656 KB |
| testcase_27 | AC | 1,419 ms
15,076 KB |
| testcase_28 | AC | 1,326 ms
15,228 KB |
| testcase_29 | AC | 897 ms
12,068 KB |
| testcase_30 | AC | 2,196 ms
18,980 KB |
| testcase_31 | AC | 2,314 ms
19,032 KB |
| testcase_32 | AC | 2,192 ms
18,828 KB |
| testcase_33 | AC | 2,202 ms
18,956 KB |
| testcase_34 | AC | 2,198 ms
18,948 KB |
| testcase_35 | AC | 2 ms
6,820 KB |
| testcase_36 | AC | 2 ms
6,820 KB |
| testcase_37 | AC | 2 ms
6,816 KB |
| testcase_38 | AC | 2 ms
6,820 KB |
| testcase_39 | AC | 2 ms
6,816 KB |
| testcase_40 | AC | 2 ms
6,820 KB |
| testcase_41 | AC | 2 ms
6,820 KB |
ソースコード
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#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();
}