QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#792161 | #9278. Linear Algebra Intensifies | bulijiojiodibuliduo# | AC ✓ | 595ms | 85576kb | C++17 | 5.1kb | 2024-11-29 02:13:08 | 2024-11-29 02:13:08 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod=998244353;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head
template<int MOD, int RT> struct mint {
static const int mod = MOD;
static constexpr mint rt() { return RT; } // primitive root for FFT
int v; explicit operator int() const { return v; } // explicit -> don't silently convert to int
mint():v(0) {}
mint(ll _v) { v = int((-MOD < _v && _v < MOD) ? _v : _v % MOD);
if (v < 0) v += MOD; }
bool operator==(const mint& o) const {
return v == o.v; }
friend bool operator!=(const mint& a, const mint& b) {
return !(a == b); }
friend bool operator<(const mint& a, const mint& b) {
return a.v < b.v; }
mint& operator+=(const mint& o) {
if ((v += o.v) >= MOD) v -= MOD;
return *this; }
mint& operator-=(const mint& o) {
if ((v -= o.v) < 0) v += MOD;
return *this; }
mint& operator*=(const mint& o) {
v = int((ll)v*o.v%MOD); return *this; }
mint& operator/=(const mint& o) { return (*this) *= inv(o); }
friend mint pow(mint a, ll p) {
mint ans = 1; assert(p >= 0);
for (; p; p /= 2, a *= a) if (p&1) ans *= a;
return ans; }
friend mint inv(const mint& a) { assert(a.v != 0);
return pow(a,MOD-2); }
mint operator-() const { return mint(-v); }
mint& operator++() { return *this += 1; }
mint& operator--() { return *this -= 1; }
friend mint operator+(mint a, const mint& b) { return a += b; }
friend mint operator-(mint a, const mint& b) { return a -= b; }
friend mint operator*(mint a, const mint& b) { return a *= b; }
friend mint operator/(mint a, const mint& b) { return a /= b; }
};
const int MOD=998244353;
using mi = mint<MOD,5>; // 5 is primitive root for both common mods
namespace simp {
vector<mi> fac,ifac,invn;
void check(int x) {
if (fac.empty()) {
fac={mi(1),mi(1)};
ifac={mi(1),mi(1)};
invn={mi(0),mi(1)};
}
while (SZ(fac)<=x) {
int n=SZ(fac),m=SZ(fac)*2;
fac.resize(m);
ifac.resize(m);
invn.resize(m);
for (int i=n;i<m;i++) {
fac[i]=fac[i-1]*mi(i);
invn[i]=mi(MOD-MOD/i)*invn[MOD%i];
ifac[i]=ifac[i-1]*invn[i];
}
}
}
mi gfac(int x) {
assert(x>=0);
check(x); return fac[x];
}
mi ginv(int x) {
assert(x>0);
check(x); return invn[x];
}
mi gifac(int x) {
assert(x>=0);
check(x); return ifac[x];
}
mi binom(int n,int m) {
if (m < 0 || m > n) return mi(0);
return gfac(n)*gifac(m)*gifac(n - m);
}
mi binombf(int n,int m) {
if (m < 0 || m > n) return mi(0);
if (m>n-m) m=n-m;
mi p=1,q=1;
for (int i=1;i<=m;i++) p=p*(n+1-i),q=q*i;
return p/q;
}
}
const int N=501000;
int f[N],n,m,id[N];
set<PII> e[N];
mi g[1111][1111];
mi det(vector<vector<mi>> f) {
int n=SZ(f);
mi ans=1;
rep(i,0,n) {
bool fg=0;
rep(j,i,n) {
if (f[j][i]!=0) {
rep(k,i,n) swap(f[i][k],f[j][k]);
if (j!=i) ans*=-1;
fg=1;
break;
}
}
if (!fg) return 0;
mi v=1/(-f[i][i]);
rep(j,i+1,n) {
mi tmp=f[j][i]*v;
rep(k,i,n) f[j][k]=(f[j][k]+tmp*f[i][k]);
}
}
rep(i,0,n) ans=ans*f[i][i];
return ans;
}
int find(int x) {
return f[x]==x?x:f[x]=find(f[x]);
}
int main() {
scanf("%d%d",&n,&m);
rep(i,0,n+1) f[i]=i;
rep(i,0,m) {
int u,v;
scanf("%d%d",&u,&v);
--u;
f[find(u)]=find(v);
e[u].insert(mp(v,i));
e[v].insert(mp(u,i));
}
rep(i,0,n+1) if (find(i)!=find(0)) {
puts("0");
return 0;
}
if (m==n) {
puts("1");
return 0;
}
queue<int> q;
rep(i,0,n+1) {
if (SZ(e[i])==1) q.push(i);
}
while (!q.empty()) {
auto u=q.front(); q.pop();
auto [v,w]=*e[u].begin();
assert(e[v].count(mp(u,w)));
e[v].erase(mp(u,w));
e[u].clear();
if (SZ(e[v])==1) {
q.push(v);
}
}
VI pv;
int c2=0;
rep(i,0,n+1) {
if (SZ(e[i])>=3) {
pv.pb(i);
id[i]=SZ(pv);
}
if (SZ(e[i])==2) c2++;
}
if (pv.empty()) {
printf("%d\n",c2);
return 0;
}
mi ans=1;
VI selfv;
auto addeg=[&](int u,int v,int w) {
u=id[u]-1; v=id[v]-1;
selfv.pb(w);
if (u==v) return;
mi iw=mi(1)/mi(w);
g[u][u]+=iw;
g[u][v]-=iw;
};
function<void(int,int,int,int)> dfs=[&](int u,int par,int dep,int rt) {
if (dep>0&&id[u]) {
addeg(rt,u,dep);
return;
}
for (auto [v,w]:e[u]) if (w!=par) {
dfs(v,w,dep+1,rt);
}
};
for (auto u:pv) dfs(u,-1,0,u);
vector<vector<mi>> ff;
rep(i,1,SZ(pv)) ff.pb(vector<mi>(g[i]+1,g[i]+SZ(pv)));
ans=ans*det(ff);
sort(all(selfv));
for (int i=0;i<SZ(selfv);i+=2) ans=ans*selfv[i];
printf("%d\n",(int)ans);
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 6ms
memory: 34708kb
input:
3 4 1 2 2 3 1 2 3 3
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 0
Accepted
time: 8ms
memory: 34692kb
input:
1 1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 4ms
memory: 34540kb
input:
1 10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
output:
10
result:
ok 1 number(s): "10"
Test #4:
score: 0
Accepted
time: 0ms
memory: 35164kb
input:
2 1 1 2
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 0ms
memory: 35116kb
input:
2 2 1 2 1 1
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 4ms
memory: 35848kb
input:
2 3 1 1 2 2 1 2
output:
3
result:
ok 1 number(s): "3"
Test #7:
score: 0
Accepted
time: 0ms
memory: 34808kb
input:
12 23 10 12 6 12 3 6 3 4 5 12 10 10 10 11 9 9 8 12 4 12 1 9 4 9 2 2 10 11 5 12 8 12 9 9 1 9 6 12 10 10 2 2 3 6 3 4
output:
3072
result:
ok 1 number(s): "3072"
Test #8:
score: 0
Accepted
time: 0ms
memory: 35712kb
input:
2 10 1 2 2 2 1 1 1 1 1 2 1 1 1 2 2 2 2 2 1 2
output:
33
result:
ok 1 number(s): "33"
Test #9:
score: 0
Accepted
time: 0ms
memory: 35324kb
input:
9 20 4 6 9 9 8 9 3 3 2 8 6 8 9 9 2 6 2 8 1 1 2 4 1 2 5 9 1 3 2 7 1 3 1 6 2 3 2 8 2 6
output:
3696
result:
ok 1 number(s): "3696"
Test #10:
score: 0
Accepted
time: 0ms
memory: 36252kb
input:
109 245 6 57 29 81 21 76 21 76 36 44 53 71 29 29 43 78 1 12 26 50 3 100 8 84 30 103 1 21 61 76 19 78 37 55 78 79 15 64 18 53 40 82 28 66 14 40 30 63 53 85 64 106 1 95 87 106 14 36 8 84 30 64 40 82 9 62 29 50 68 87 48 64 63 105 1 17 15 66 26 50 1 48 50 75 52 75 10 10 74 106 9 75 65 102 91 103 12 83 6...
output:
589921054
result:
ok 1 number(s): "589921054"
Test #11:
score: 0
Accepted
time: 0ms
memory: 34820kb
input:
100 100 46 100 45 92 86 97 72 78 44 79 35 97 31 92 88 93 49 89 12 56 7 63 58 86 51 70 81 100 33 37 29 94 12 38 31 53 26 90 77 96 10 88 26 69 44 90 6 48 37 47 60 77 32 42 40 41 50 83 83 90 95 100 21 33 17 62 12 91 59 68 63 82 11 60 48 98 5 47 56 60 1 95 38 52 25 66 51 59 4 33 95 96 55 74 26 93 25 68 ...
output:
1
result:
ok 1 number(s): "1"
Test #12:
score: 0
Accepted
time: 4ms
memory: 35156kb
input:
122 123 4 37 48 73 21 96 68 84 43 94 11 36 38 113 40 108 65 81 10 111 6 19 80 92 37 40 40 122 60 113 2 19 29 31 26 75 33 68 27 69 51 65 17 90 88 112 56 68 46 46 83 110 25 80 14 38 101 108 16 41 64 89 19 88 76 87 26 79 51 90 107 119 7 17 71 100 17 59 14 105 15 26 22 95 113 117 22 91 19 99 57 119 42 5...
output:
123
result:
ok 1 number(s): "123"
Test #13:
score: 0
Accepted
time: 9ms
memory: 34688kb
input:
99 200 53 74 10 80 6 73 73 81 7 37 81 93 12 55 6 40 24 96 86 89 48 89 17 75 20 65 18 52 36 89 8 24 29 33 53 72 28 45 27 35 38 73 11 41 74 76 73 86 87 93 11 73 4 19 80 88 11 80 12 21 13 86 69 78 3 18 32 47 3 49 50 93 30 60 8 19 26 70 1 62 9 96 58 94 25 35 42 91 61 70 13 96 10 44 57 73 19 85 16 37 81 ...
output:
560526429
result:
ok 1 number(s): "560526429"
Test #14:
score: 0
Accepted
time: 32ms
memory: 35692kb
input:
3000 3300 203 2193 755 2277 2141 2736 1115 1127 82 1944 573 2600 1063 1949 375 1712 395 999 950 1690 52 1226 560 2924 83 1464 1504 2104 10 986 64 1331 1631 1755 573 2344 1615 1737 2414 2804 480 2113 2174 2909 666 2914 156 1588 611 1533 528 1285 1004 2763 19 80 73 1954 777 1297 2116 2117 186 847 1056...
output:
855511535
result:
ok 1 number(s): "855511535"
Test #15:
score: 0
Accepted
time: 291ms
memory: 82736kb
input:
500000 500000 106843 246711 220148 499250 169638 287414 348384 439218 464123 485715 242531 404366 304063 470177 158965 188123 11671 470956 441213 450178 229736 319036 393409 440552 204883 324026 476519 481812 444616 468853 65586 178690 234265 263137 434457 470186 391493 410684 329022 357803 139095 4...
output:
1
result:
ok 1 number(s): "1"
Test #16:
score: 0
Accepted
time: 0ms
memory: 35856kb
input:
500000 1 301721 361047
output:
0
result:
ok 1 number(s): "0"
Test #17:
score: 0
Accepted
time: 289ms
memory: 82844kb
input:
500000 500000 98619 388571 341253 371055 201469 217888 92958 138959 14275 185016 76593 118908 448437 499659 101559 211959 162147 291039 114239 445451 218665 248802 3153 359183 256945 314214 393034 477015 204725 291777 421118 494553 439455 467768 71748 416919 203928 245846 430083 470965 354933 476142...
output:
0
result:
ok 1 number(s): "0"
Test #18:
score: 0
Accepted
time: 257ms
memory: 82688kb
input:
500000 500000 177093 360397 302589 367660 85299 288630 199827 242302 141963 328163 135504 138139 198476 308433 228887 382116 168447 190268 5588 231484 281079 307027 195125 362060 185089 293372 22610 208438 69594 330179 146715 479740 200305 464094 307384 448176 298448 439901 116418 402473 219948 4371...
output:
1
result:
ok 1 number(s): "1"
Test #19:
score: 0
Accepted
time: 293ms
memory: 82796kb
input:
499700 500000 199312 363387 28170 45801 218790 419838 88326 324416 118422 432158 153235 242162 11579 25299 223249 486090 163817 497246 187168 389868 95567 450717 6783 57079 266046 342045 426586 484374 31227 41797 53367 462151 221528 339573 183106 374349 99554 405978 191158 417963 215600 248217 16628...
output:
0
result:
ok 1 number(s): "0"
Test #20:
score: 0
Accepted
time: 583ms
memory: 83532kb
input:
499700 500000 21935 291497 3024 478103 245079 313731 289382 445058 7336 28195 78312 277188 1478 444596 110770 303251 305814 488077 392299 458444 49934 365673 98804 210611 284717 482990 169781 473469 80921 280809 2832 31209 117964 355575 80469 280739 120148 145950 99614 451361 139980 305651 273769 47...
output:
780759157
result:
ok 1 number(s): "780759157"
Test #21:
score: 0
Accepted
time: 244ms
memory: 82904kb
input:
499999 500000 337206 367714 166297 312794 307170 414738 110332 372626 212936 344573 168963 205236 160790 386652 365877 467290 72766 300544 174237 422273 101731 241073 398746 416888 456126 491059 210317 263195 109345 295637 231932 408374 52853 329207 334163 388929 125157 486076 197084 206788 292973 3...
output:
500000
result:
ok 1 number(s): "500000"
Test #22:
score: 0
Accepted
time: 384ms
memory: 74140kb
input:
400025 400325 347626 347915 4781 209476 30074 115935 143154 195884 3575 344617 247862 261061 135176 255423 178268 222368 247067 286708 340084 343728 188171 281733 41990 240994 255351 374129 165903 171225 9259 185918 137286 212423 126850 376328 62992 189751 34847 36098 8890 163372 106962 373854 44874...
output:
539971491
result:
ok 1 number(s): "539971491"
Test #23:
score: 0
Accepted
time: 284ms
memory: 64588kb
input:
300109 300400 6455 97886 125279 267449 21281 149096 216607 281358 46405 175071 12597 165532 10905 37179 125605 180980 120823 167319 90076 114751 190919 266219 107082 251302 109232 140660 128428 290381 42195 272858 131018 164771 22552 238723 229759 290134 55034 182192 37207 108904 4740 23439 20378 18...
output:
882836819
result:
ok 1 number(s): "882836819"
Test #24:
score: 0
Accepted
time: 500ms
memory: 83664kb
input:
499999 500000 47849 283106 16634 475213 1354 212127 123209 162917 271573 285753 338710 487415 160493 268905 237678 347030 132405 308987 130542 314305 343555 386154 142357 300413 100571 197171 43107 62217 142052 435822 86940 157935 202074 254928 39505 184155 55872 351366 42763 363981 182118 360911 68...
output:
2
result:
ok 1 number(s): "2"
Test #25:
score: 0
Accepted
time: 491ms
memory: 82844kb
input:
490100 490400 156712 369932 385830 470289 422686 451652 211899 262956 147118 481327 122259 164629 334205 483114 163904 402960 338978 484787 283943 460768 57259 267931 75630 163562 178413 449536 357293 395320 107150 197041 82435 265012 379336 474275 389629 468275 297678 336271 101433 247320 18671 170...
output:
418567388
result:
ok 1 number(s): "418567388"
Test #26:
score: 0
Accepted
time: 438ms
memory: 79200kb
input:
450004 450304 32697 266011 425030 429101 316811 401885 31452 257565 35162 192946 30486 291145 35013 345381 345937 399617 147064 304884 234469 347087 104761 122260 73712 324726 118741 271448 29319 57779 120877 341625 234063 274395 35730 154243 25603 208972 256148 381349 155824 206927 25196 56453 1763...
output:
620981594
result:
ok 1 number(s): "620981594"
Test #27:
score: 0
Accepted
time: 486ms
memory: 82892kb
input:
490009 490309 134383 158561 156596 248554 191181 207375 39398 414704 31355 371571 240548 438664 165053 318372 10295 107721 182673 223226 159451 448204 71681 113596 172222 405158 144438 339534 101556 358403 29436 350332 32362 84576 57221 112349 108311 202303 11882 476684 484463 489184 224724 282924 2...
output:
566276003
result:
ok 1 number(s): "566276003"
Test #28:
score: 0
Accepted
time: 490ms
memory: 84076kb
input:
490298 490598 210225 404229 2951 362841 331483 485378 6529 480859 167203 226530 1488 177457 316845 346894 103830 163223 150926 194319 201991 252388 133043 370380 245639 248027 116641 417488 121251 311507 75808 241313 1348 331818 89022 181089 339919 446073 169128 200082 57271 59144 64237 424354 55042...
output:
343584604
result:
ok 1 number(s): "343584604"
Test #29:
score: 0
Accepted
time: 559ms
memory: 82928kb
input:
494866 495166 99825 232759 23420 274946 118866 338316 31631 397272 63794 348843 252078 420375 268070 449517 49092 417443 101604 162354 131228 170520 162201 369566 151474 439659 138548 402129 263855 444394 294741 440276 99438 212690 307 417110 405833 410540 299797 300068 70745 259694 287090 287906 86...
output:
23165905
result:
ok 1 number(s): "23165905"
Test #30:
score: 0
Accepted
time: 569ms
memory: 82616kb
input:
469734 470032 24842 37234 179928 432668 310523 336074 207102 290436 144971 226528 239653 437703 196160 405776 25708 266051 156570 443810 87313 314748 83805 175806 282070 381371 218911 243720 74897 80691 103233 276556 116766 172090 24668 272161 6529 98246 123656 378790 241432 446852 191128 324209 163...
output:
195465029
result:
ok 1 number(s): "195465029"
Test #31:
score: 0
Accepted
time: 488ms
memory: 81208kb
input:
469635 469935 333845 352288 199361 346371 129944 208644 61813 329773 139360 242410 253496 406352 43353 412465 130631 192408 192634 423222 130374 322955 83713 441275 270897 464813 412276 467854 412007 469177 185122 261975 111619 180110 292090 415208 36210 447557 15978 348190 58491 405604 154543 34094...
output:
760746584
result:
ok 1 number(s): "760746584"
Test #32:
score: 0
Accepted
time: 595ms
memory: 85576kb
input:
499700 500000 358992 469294 340849 470072 189441 384117 172296 337350 131713 272631 67378 370126 79109 92814 98012 268753 232750 389178 136053 489605 57409 59870 90630 101473 206752 447545 58837 344696 249290 256036 99843 216684 339015 429470 432 35563 8275 436125 122868 401278 264824 324538 310668 ...
output:
253203006
result:
ok 1 number(s): "253203006"
Test #33:
score: 0
Accepted
time: 501ms
memory: 84612kb
input:
499039 499339 159987 251448 124976 310641 106470 220204 362424 484869 340457 433213 21659 102293 273684 325859 116000 360085 42835 443988 110794 227293 175656 495481 72767 188171 110287 123811 201406 239266 34357 220978 117450 172353 215053 259162 360436 469884 110074 277892 120457 342858 141315 171...
output:
71926140
result:
ok 1 number(s): "71926140"
Extra Test:
score: 0
Extra Test Passed