QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #297627 | #5826. 错排 | chenxinyang2006 | 100 ✓ | 542ms | 20728kb | C++14 | 4.9kb | 2024-01-04 20:55:39 | 2024-01-04 20:55:40 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;
template <class T>
void chkmax(T &x,T y){
if(x < y) x = y;
}
template <class T>
void chkmin(T &x,T y){
if(x > y) x = y;
}
inline int popcnt(int x){
return __builtin_popcount(x);
}
inline int ctz(int x){
return __builtin_ctz(x);
}
template <int P>
class mod_int
{
using Z = mod_int;
private:
static int mo(int x) { return x < 0 ? x + P : x; }
public:
int x;
int val() const { return x; }
mod_int() : x(0) {}
template <class T>
mod_int(const T &x_) : x(x_ >= 0 && x_ < P ? static_cast<int>(x_) : mo(static_cast<int>(x_ % P))) {}
bool operator==(const Z &rhs) const { return x == rhs.x; }
bool operator!=(const Z &rhs) const { return x != rhs.x; }
Z operator-() const { return Z(x ? P - x : 0); }
Z pow(long long k) const
{
Z res = 1, t = *this;
while (k)
{
if (k & 1)
res *= t;
if (k >>= 1)
t *= t;
}
return res;
}
Z &operator++()
{
x < P - 1 ? ++x : x = 0;
return *this;
}
Z &operator--()
{
x ? --x : x = P - 1;
return *this;
}
Z operator++(int)
{
Z ret = x;
x < P - 1 ? ++x : x = 0;
return ret;
}
Z operator--(int)
{
Z ret = x;
x ? --x : x = P - 1;
return ret;
}
Z inv() const { return pow(P - 2); }
Z &operator+=(const Z &rhs)
{
(x += rhs.x) >= P && (x -= P);
return *this;
}
Z &operator-=(const Z &rhs)
{
(x -= rhs.x) < 0 && (x += P);
return *this;
}
Z operator-()
{
return -x;
}
Z &operator*=(const Z &rhs)
{
x = 1ULL * x * rhs.x % P;
return *this;
}
Z &operator/=(const Z &rhs) { return *this *= rhs.inv(); }
#define setO(T, o) \
friend T operator o(const Z &lhs, const Z &rhs) \
{ \
Z res = lhs; \
return res o## = rhs; \
}
setO(Z, +) setO(Z, -) setO(Z, *) setO(Z, /)
#undef setO
friend istream& operator>>(istream& is, mod_int& x)
{
long long tmp;
is >> tmp;
x = tmp;
return is;
}
friend ostream& operator<<(ostream& os, const mod_int& x)
{
os << x.val();
return os;
}
};
using Z = mod_int<mod>;
Z power(Z p,ll k){
Z ans = 1;
while(k){
if(k % 2 == 1) ans *= p;
p *= p;
k /= 2;
}
return ans;
}
Z fact[1000005],ifac[1000005],inv[1000005];
Z C(int N,int M){
if(N < M || M < 0) return 0;
return fact[N] * ifac[M] * ifac[N - M];
}
void init(int L){
fact[0] = 1;
rep(i,1,L) fact[i] = fact[i - 1] * i;
ifac[L] = 1 / fact[L];
per(i,L - 1,0) ifac[i] = ifac[i + 1] * (i + 1);
rep(i,1,L) inv[i] = ifac[i] * fact[i - 1];
}
int T;
Z result[200005],D[200005];
struct qry{
int p,q,id;
};
const int B = 450,V = 200000;
inline int from(int x){
return (x + B - 1) / B;
}
inline int L(int x){
return x * B - B + 1;
}
vector <qry> Q[4005];
bool cmp(qry _a,qry _b){
return _a.q < _b.q;
}
int n,m;
Z x,y;
void addn(){
x = C(m,n + 2) + (n + 1) * (x + y) - m * x;
swap(x,y);
n++;
}
void subn(){
n--;
y = (y - C(m,n + 2) - (n + 1) * x) * inv[n + 1 - m];
swap(x,y);
}
void addm(){
Z temp = (y - m * x - C(m,n + 1)) * inv[n - m];
y = x + y;
x = temp;
m++;
}
int main(){
// freopen("test.in","r",stdin);
scanf("%d",&T);
init(V);
D[0] = 1;D[1] = 0;
rep(i,2,V) D[i] = (i - 1) * (D[i - 1] + D[i - 2]);
rep(i,1,T){
int p,q;
scanf("%d%d",&p,&q);
p -= q;
if(p < q) continue;
Q[from(p)].push_back({p,q,i});
// printf("%d %d\n",p,q);
}
rep(p,1,from(V)){
n = L(p);m = 0;
x = D[n];y = D[n + 1];
sort(Q[p].begin(),Q[p].end(),cmp);
for(qry cur:Q[p]){
while(n < cur.p) addn();
while(n > cur.p) subn();
while(m < cur.q) addm();
// printf("%d %d %d %d\n",n,m,x.val(),y.val());
result[cur.id] = x * fact[cur.p] * ifac[cur.p - cur.q];
}
}
rep(i,1,T) printf("%d\n",result[i].val());
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 1
Accepted
Test #1:
score: 1
Accepted
time: 0ms
memory: 16756kb
input:
0
output:
result:
ok 0 number(s): ""
Subtask #2:
score: 9
Accepted
Test #2:
score: 9
Accepted
time: 0ms
memory: 17092kb
input:
10 8 6 5 1 4 2 6 3 8 1 3 1 6 2 3 1 4 1 6 2
output:
0 44 4 36 14833 2 168 2 9 168
result:
ok 10 numbers
Test #3:
score: 0
Accepted
time: 4ms
memory: 16968kb
input:
10 8 1 8 4 6 3 8 2 8 3 6 3 6 1 7 3 2 1 8 3
output:
14833 576 36 10860 4680 36 265 432 1 4680
result:
ok 10 numbers
Test #4:
score: 0
Accepted
time: 3ms
memory: 17004kb
input:
10 7 5 3 1 8 3 7 3 8 1 4 1 5 2 6 3 7 1 7 3
output:
0 2 4680 432 14833 9 24 36 1854 432
result:
ok 10 numbers
Test #5:
score: 0
Accepted
time: 4ms
memory: 16944kb
input:
10 7 2 8 4 6 1 5 1 8 2 6 3 4 2 8 3 3 1 8 1
output:
1280 576 265 44 10860 36 4 4680 2 14833
result:
ok 10 numbers
Test #6:
score: 0
Accepted
time: 4ms
memory: 17248kb
input:
10 6 6 3 1 8 3 2 1 7 1 3 1 6 2 8 4 7 3 7 0
output:
0 2 4680 1 1854 2 168 576 432 1854
result:
ok 10 numbers
Subtask #3:
score: 10
Accepted
Test #7:
score: 10
Accepted
time: 47ms
memory: 19696kb
input:
200000 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 10 0 11 0 12 0 13 0 14 0 15 0 16 0 17 0 18 0 19 0 20 0 21 0 22 0 23 0 24 0 25 0 26 0 27 0 28 0 29 0 30 0 31 0 32 0 33 0 34 0 35 0 36 0 37 0 38 0 39 0 40 0 41 0 42 0 43 0 44 0 45 0 46 0 47 0 48 0 49 0 50 0 51 0 52 0 53 0 54 0 55 0 56 0 57 0 58 0 59 0 60 0 61...
output:
0 1 2 9 44 265 1854 14833 133496 1334961 14684570 176214841 294304226 127281753 910981941 600290115 222488424 11814221 224470198 496426549 442513998 751108780 305347938 340640042 530046225 804025262 745550660 910531421 451058030 554564312 221339670 95158970 145512950 954462889 464137465 737039093 31...
result:
ok 200000 numbers
Subtask #4:
score: 20
Accepted
Test #8:
score: 20
Accepted
time: 283ms
memory: 19792kb
input:
200000 4303 1473 1276 72 967 234 3619 984 1316 384 2679 50 4426 1744 3782 1179 4919 4 805 63 3933 158 1574 528 1277 435 3826 915 2739 68 2286 349 3017 527 3036 476 4280 1764 1504 686 4584 917 1379 145 4764 2178 1881 45 4808 1565 3663 165 4730 2209 2258 103 4181 1687 1636 770 4339 1173 2355 777 3201 ...
output:
855518783 202627962 284771116 596280162 111952425 28114068 922980998 483503998 478475869 42227903 210453242 82826277 349706660 478397018 588903665 672339856 911511930 783922264 224272260 199537336 659467844 383745708 953695418 668329703 880293299 649430530 916687905 550953325 295023552 141584429 871...
result:
ok 200000 numbers
Test #9:
score: 0
Accepted
time: 279ms
memory: 19864kb
input:
200000 4558 644 2015 866 4752 1612 4343 704 4455 1277 4761 1069 1173 434 2150 1002 3226 132 4556 1468 4362 2008 3194 936 4750 1712 4133 58 4670 2111 3787 1705 1006 458 4973 1489 2520 934 3971 1256 4130 522 1648 28 4843 1800 3535 1031 2363 345 2722 1187 4620 1677 3738 325 3783 447 2026 617 4992 1595 ...
output:
878092359 137664342 571257477 157127504 385052631 35779181 650061801 617898174 375209372 721222702 707783783 410748088 991469920 69775359 76681433 134815341 199607624 126498594 149881281 563970794 786560573 94902562 668383803 802669973 229778708 749799553 295203934 163664840 140841030 547218181 2572...
result:
ok 200000 numbers
Test #10:
score: 0
Accepted
time: 278ms
memory: 19884kb
input:
200000 4763 4669 4281 319 1441 342 1078 224 2092 1022 1666 78 2623 660 4797 1258 4878 1616 3255 931 619 85 3632 220 3163 1358 4177 1838 3072 746 938 59 4038 1283 3825 618 4889 1090 3988 1380 686 237 4488 139 3189 572 4790 263 2862 340 3325 261 2351 1141 3047 659 2562 445 4947 1894 2504 717 3399 1176...
output:
0 283193141 728175842 611328334 18202018 506844457 979367956 585351167 337548843 72363572 243634086 313739474 707317304 637199005 278105669 961177961 957750794 767835509 349772711 198594249 245831996 37104891 398916514 263271106 843118755 308147020 690301962 174120745 179202564 216399429 946430481 7...
result:
ok 200000 numbers
Test #11:
score: 0
Accepted
time: 271ms
memory: 19920kb
input:
200000 1079 17 495 169 2890 659 3047 174 3199 761 2190 375 1947 159 4965 614 4463 1910 3630 321 4253 574 3175 871 2697 1262 3957 455 3435 205 2640 4 2181 935 1712 162 1152 351 3230 288 3887 1633 1094 374 833 295 3987 1856 844 179 2218 178 4922 683 4637 1988 2952 384 1493 720 4479 239 3366 1065 3663 ...
output:
158255419 402786997 811229485 767930818 68320941 852585187 491766976 228169531 315305063 656254912 979729105 514370258 749323558 931029769 871820770 342080940 688359960 983900818 13404663 552784020 781611444 697598838 340229841 78829168 776783084 20633291 315417596 788999254 586658522 557773549 5532...
result:
ok 200000 numbers
Test #12:
score: 0
Accepted
time: 279ms
memory: 19660kb
input:
200000 2864 223 4155 1498 2880 894 3933 1830 4207 973 2290 684 3522 1032 3713 910 4110 1341 4991 1550 4116 695 2484 943 2630 243 4943 418 1912 812 4457 2146 4979 678 1731 834 2555 625 3686 310 299 45 396 170 2876 997 4163 1859 4463 985 1617 450 4895 2328 2672 1177 3513 262 3843 1901 3070 1484 4954 1...
output:
629916892 381928609 997446852 27448639 502566091 127425081 674803798 840491154 578725589 88000079 914879351 221195824 389963150 790633997 798572067 76424829 35810515 100952206 612109651 277816564 59895360 717456537 370024748 46166162 89317834 803273270 844790653 676215132 402126887 644239704 5667377...
result:
ok 200000 numbers
Subtask #5:
score: 20
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Test #13:
score: 20
Accepted
time: 5ms
memory: 17020kb
input:
10 94764 1149 111140 21372 59140 20928 73376 27175 59837 4344 160865 25705 44518 10326 145794 64106 147628 12887 103719 39458
output:
139176963 393241499 258873190 39229362 870875380 975228452 243360193 751148936 95574458 297629235
result:
ok 10 numbers
Test #14:
score: 0
Accepted
time: 12ms
memory: 17228kb
input:
10 158002 80444 9451 2903 173427 12416 137154 16538 166581 24311 127365 41216 190696 67064 103832 40293 108767 52320 109966 50541
output:
0 702735124 750025710 841222658 375040035 583566228 649803213 746573713 113561055 257165994
result:
ok 10 numbers
Test #15:
score: 0
Accepted
time: 4ms
memory: 17012kb
input:
10 116222 34542 164940 69028 129899 24339 178863 5716 55643 22577 198734 88929 133306 14275 81416 35799 63999 8310 161489 76991
output:
290743004 378341801 539453217 748305238 182916741 547729744 354427924 684683519 325465086 252320707
result:
ok 10 numbers
Test #16:
score: 0
Accepted
time: 6ms
memory: 17008kb
input:
10 195516 163316 189541 26309 135594 44847 135877 65724 130088 25449 43733 28 99690 16935 64787 30191 71441 7633 149688 65415
output:
0 913189292 577808221 197261625 42734325 96320751 700077354 534988269 607854165 915606441
result:
ok 10 numbers
Test #17:
score: 0
Accepted
time: 5ms
memory: 17060kb
input:
10 163009 107578 44973 3654 143223 16359 94260 46849 30253 4092 157914 12798 96468 10458 69392 15738 175738 45794 88177 40742
output:
0 3532506 560207666 853291572 71222878 859859971 982136558 976170384 963781875 378642896
result:
ok 10 numbers
Test #18:
score: 0
Accepted
time: 8ms
memory: 17008kb
input:
10 110588 39549 80716 17407 111961 32201 141172 69526 113156 9733 197619 33476 175704 25422 193136 84984 121758 34704 186415 47390
output:
365752740 457468561 833768060 154200192 143999958 497510358 149082994 737572231 779740562 243498597
result:
ok 10 numbers
Test #19:
score: 0
Accepted
time: 4ms
memory: 16960kb
input:
10 135555 22650 164492 12323 142156 56953 147138 39540 198672 13148 113977 32999 140219 50353 70617 28677 163824 34306 189792 79678
output:
607236911 240877911 474627738 535731583 760041723 433248274 681491153 764919295 435671865 90602437
result:
ok 10 numbers
Test #20:
score: 0
Accepted
time: 9ms
memory: 16960kb
input:
10 170490 75332 171298 50434 192270 14874 169646 26194 148215 47449 184554 54250 89981 14289 155225 40485 117440 37074 176617 25601
output:
674081939 124446215 364039988 511947341 952033804 203192142 723185949 644885639 266757734 667462943
result:
ok 10 numbers
Subtask #6:
score: 40
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Dependency #5:
100%
Accepted
Test #21:
score: 40
Accepted
time: 542ms
memory: 20224kb
input:
200000 116981 113520 172984 9623 120214 41802 35441 7658 125295 16281 120632 38799 94733 40963 163417 9731 108251 26857 43645 17875 169121 11771 192157 44937 156107 4478 172659 1215 21630 5509 180747 8002 99036 36589 169002 3282 164290 22013 21467 2652 87429 27041 130629 53668 189321 51108 131178 48...
output:
0 373133776 31058449 989109730 803614455 180979333 732807821 644897929 772152083 175984190 387927644 392431067 195974551 886113191 804218781 215619314 673725862 773460699 366987062 18627419 578310572 573968125 744788798 487920729 483813621 131506787 504824040 771762638 31619778 83125531 916820412 65...
result:
ok 200000 numbers
Test #22:
score: 0
Accepted
time: 541ms
memory: 20424kb
input:
200000 58735 1850 169313 2805 63277 12304 147402 19719 187888 87477 74819 18981 190635 83199 33687 1605 175708 120 189436 93941 124814 57582 143173 32774 142008 5664 122032 30392 150443 63311 150455 20246 195920 6371 142158 3235 117206 55721 107020 50483 164714 76052 149700 20331 128904 48947 81621 ...
output:
236672962 601234830 754745066 308583007 994497077 368994539 422822924 482962132 921734832 984335100 345218837 522046656 946034293 366000600 37458773 476984009 923935895 879277375 280757854 800390082 835816840 859659545 129134970 174049688 116701927 329030841 450740175 105698992 286444292 9160901 829...
result:
ok 200000 numbers
Test #23:
score: 0
Accepted
time: 535ms
memory: 20016kb
input:
200000 113004 42640 55633 12884 150336 62686 101444 8848 187371 36334 197007 65729 190956 87847 176390 79860 158036 62757 169379 82974 166801 24735 162643 22108 136470 55083 123667 20863 173819 85200 109958 3401 167748 10419 112974 39455 164670 1113 85508 26792 99366 43493 121019 54707 128303 43668 ...
output:
927359447 414303248 802702133 29639537 402929075 719604306 457783089 435431407 808338876 604145604 229497738 369198002 496943127 543475586 795267068 520249848 248140567 586064482 848901904 537186736 212193232 971962559 600396573 514077589 138777802 453137609 891545655 134883831 519227986 647527934 2...
result:
ok 200000 numbers
Test #24:
score: 0
Accepted
time: 535ms
memory: 20020kb
input:
200000 179437 79333 126421 8791 196178 69519 172133 48117 183063 44825 197242 24274 91029 28463 80201 39267 192934 67382 164408 69349 189396 57001 135514 4064 193807 9420 175019 82959 194775 42011 113853 50366 148778 17354 115323 53286 187487 59960 106561 34605 183861 55467 35368 10274 77631 23942 1...
output:
795281687 114601455 89944816 682847629 457542171 837970706 830500797 303647451 906425981 593003508 637635196 229058959 401065599 809693259 797571551 847067655 415885981 753944162 161063381 709924207 646505777 676919931 749629361 77356758 921561629 667879408 971324122 309738294 654099446 277711857 37...
result:
ok 200000 numbers
Test #25:
score: 0
Accepted
time: 537ms
memory: 20252kb
input:
200000 21539 20533 145383 52634 113654 30429 80064 9467 195402 77904 197681 36205 52227 19183 177962 1339 165580 55186 74230 13685 135841 15403 109658 37070 193318 5890 115482 40324 170583 14764 195738 5537 155151 59554 66090 2269 163822 30482 138338 56447 156072 27707 154951 31009 158986 24872 1118...
output:
0 479960072 243081397 767418170 517280565 108177535 565902752 924595750 673374466 363526813 184539955 948059374 357770882 942605392 604372199 475126177 221606903 981887729 11462313 787129865 688306246 928964856 921770396 789081878 776455793 320496320 953984460 326577002 413919993 774559715 18311481 ...
result:
ok 200000 numbers
Test #26:
score: 0
Accepted
time: 535ms
memory: 20016kb
input:
200000 105097 78817 192914 45257 198481 88631 138540 34300 60493 1369 189308 3692 172232 41363 83155 5560 8294 2082 60124 1537 44806 17670 136239 28541 104205 31003 67286 16343 183223 44376 147375 56154 93704 18315 166491 41822 89567 13357 192031 66259 151498 19310 173814 78010 23263 8241 90623 3877...
output:
0 103239690 699572431 536983529 251415773 636484599 690138701 853603027 567531131 545578811 486228470 980256188 897379114 422596921 272994632 974878607 924018238 579739813 243888689 967574461 594989574 378700988 180701825 794923043 203297891 211275178 589012214 575623425 792601472 737984808 97348496...
result:
ok 200000 numbers
Test #27:
score: 0
Accepted
time: 541ms
memory: 20412kb
input:
200000 146194 53791 138588 55971 156629 37010 33508 14053 112421 48284 145870 67405 71102 2878 18880 4624 59718 25248 192825 25124 74102 26473 37252 16010 188000 59126 31002 5268 147784 34420 99401 14862 86995 17405 186238 59755 149926 61327 198236 13173 196060 12289 131690 56150 58101 28458 71038 8...
output:
974982799 57078985 988642904 954974882 151739762 736440874 119206325 561727481 495514245 454656815 928897819 371474861 495310514 403809331 580802962 140225208 701447778 380708125 51875098 317120055 943468131 123764123 980507258 202890807 782709603 381797665 6052296 619935818 259598993 26344139 98411...
result:
ok 200000 numbers
Test #28:
score: 0
Accepted
time: 532ms
memory: 20408kb
input:
200000 50221 20121 148424 209 166150 36682 78124 5874 163784 20976 147364 71285 193978 57077 94841 29845 90969 18387 49825 960 194594 37371 180067 11722 188506 43892 102338 1088 156134 65570 140194 5236 131184 38381 199863 64735 180721 42258 86008 5844 145651 2006 197315 96463 138858 50753 142861 63...
output:
386310721 962983293 552043755 9061643 633540591 449398563 903204836 996964187 399880294 721770237 965893401 751881501 491820162 239117565 239201422 995960018 481493770 442327710 37496721 847066165 542734774 361645814 737954610 283009588 480675384 822964684 320715713 848182977 319669655 554487536 245...
result:
ok 200000 numbers
Test #29:
score: 0
Accepted
time: 533ms
memory: 20728kb
input:
200000 165337 38779 43561 2946 92524 21713 81578 29103 60575 570 162995 70818 198362 55177 123766 44181 163177 43362 160496 17634 178111 79689 107763 9224 152590 48491 180438 30388 165896 35168 154069 53488 121785 44543 63025 6675 179104 6990 175075 51909 40893 1352 167547 71105 121800 12334 124061 ...
output:
643932217 629086470 881203123 430715603 397456033 945638273 80541402 633163409 848689838 688609415 811627985 33419803 377549373 617428636 194114815 416344257 196622239 947289103 697785550 674531104 537106537 447779894 668175293 903647322 908876994 67876699 185558402 884567420 88666097 377097358 2820...
result:
ok 200000 numbers
Test #30:
score: 0
Accepted
time: 537ms
memory: 19948kb
input:
200000 175882 19605 191921 6339 83326 11156 22250 8702 195222 37304 196980 32930 64606 1848 190716 76198 165433 46498 193009 42779 135714 27095 99238 30580 148441 73512 165607 56482 138956 31380 119162 20968 166133 70760 77774 1354 49724 23748 76384 21011 86795 28426 173421 5276 168374 69592 198345 ...
output:
446519097 976757294 810532371 497666222 387554166 892651142 905284109 35544754 795761530 96213092 421701821 672330248 93480961 64290673 28916630 879558646 727546000 172503687 824028938 306601165 506940432 657105453 64154710 798167148 41591101 599122911 346969563 742278637 33094459 814416467 24732063...
result:
ok 200000 numbers
Extra Test:
score: 0
Extra Test Passed