QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#316558 | #8180. Bridge Elimination | ucup-team2112# | TL | 1672ms | 6444kb | C++20 | 14.4kb | 2024-01-27 21:48:08 | 2024-01-27 21:48:09 |
Judging History
answer
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
using ll = long long;
int norm(int x) {
if (x < 0) {
x += mod;
}
if (x >= mod) {
x -= mod;
}
return x;
}
template<class T>
T power(T a, int b) {
T res = 1;
for (; b; b /= 2, a *= a) {
if (b % 2) {
res *= a;
}
}
return res;
}
struct mint {
int x;
mint(int x = 0) : x(norm(x)) {}
int val() const {
return x;
}
mint operator-() const {
return mint(norm(mod - x));
}
mint inv() const {
assert(x != 0);
return power(*this, mod - 2);
}
mint &operator*=(const mint &rhs) {
x = ll(x) * rhs.x % mod;
return *this;
}
mint &operator+=(const mint &rhs) {
x = norm(x + rhs.x);
return *this;
}
mint &operator-=(const mint &rhs) {
x = norm(x - rhs.x);
return *this;
}
mint &operator/=(const mint &rhs) {
return *this *= rhs.inv();
}
friend mint operator*(const mint &lhs, const mint &rhs) {
mint res = lhs;
res *= rhs;
return res;
}
friend mint operator+(const mint &lhs, const mint &rhs) {
mint res = lhs;
res += rhs;
return res;
}
friend mint operator-(const mint &lhs, const mint &rhs) {
mint res = lhs;
res -= rhs;
return res;
}
friend mint operator/(const mint &lhs, const mint &rhs) {
mint res = lhs;
res /= rhs;
return res;
}
friend std::istream &operator>>(std::istream &is, mint &a) {
ll v;
is >> v;
a = mint(v);
return is;
}
friend std::ostream &operator<<(std::ostream &os, const mint &a) {
return os << a.val();
}
};
const int maxn = 405;
mint f[maxn][maxn];
mint ff[maxn];
mint g[maxn];
mint new_g[maxn];
mint choose[maxn][maxn];
mint dp[405][405];
mint new_dp[405][405];
const int MAXN = 2048 + 5;
const int MOD = 998244353;
using LL = long long;
#define Gi 3
#define Int register int
#define mod 998244353
#define Gii 332748118
struct GO{
// inline int quick_pow (int a,int b)
// {
// int res = 1;
// for (; b; b >>= 1,a = 1ll * a * a % mod) if (b & 1) res = 1ll * res * a % mod;
// return res;
// }
// int limit,l,r[MAXN];
// inline void NTT (int *a,int type)
// {
// for (Int i = 0; i < limit; ++ i) if (i < r[i]) swap (a[i],a[r[i]]);
// for (Int mid = 1; mid < limit; mid <<= 1)
// {
// int Wn = quick_pow (type == 1 ? Gi : Gii,(mod - 1) / (mid << 1));
// for (Int R = mid << 1,j = 0; j < limit; j += R)
// {
// for (Int k = 0,w = 1; k < mid; ++ k,w = 1ll * w * Wn % mod)
// {
// int x = a[j + k],y = 1ll * w * a[j + k + mid] % mod;
// a[j + k] = (x + y) % mod,a[j + k + mid] = (x + mod - y) % mod;
// }
// }
// }
// if (type == 1) return ;
// int Inv = quick_pow (limit,mod - 2);
// for (Int i = 0; i < limit; ++ i) a[i] = 1ll * a[i] * Inv % mod;
// }
// int c[MAXN];
// inline void Solve (int len,int *a,int *b)
// {
// if (len == 1) return b[0] = quick_pow (a[0],mod - 2),void ();
// Solve ((len + 1) >> 1,a,b);
// limit = 1,l = 0;
// while (limit < (len << 1)) limit <<= 1,l ++;
// for (Int i = 0; i < limit; ++ i) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
// for (Int i = 0; i < len; ++ i) c[i] = a[i];
// for (Int i = len; i < limit; ++ i) c[i] = 0;
// NTT (c,1);
// NTT (b,1);
// for (Int i = 0; i < limit; ++ i) b[i] = 1ll * b[i] * (2 + mod - 1ll * c[i] * b[i] % mod) % mod;
// NTT (b,-1);
// for (Int i = len; i < limit; ++ i) b[i] = 0;
// }
// inline void deravitive (int *a,int n)
// {
// for (Int i = 1; i <= n; ++ i) a[i - 1] = 1ll * a[i] * i % mod;
// a[n] = 0;
// }
// inline void inter (int *a,int n)
// {
// for (Int i = n; i >= 1; -- i) a[i] = 1ll * a[i - 1] * quick_pow (i,mod - 2) % mod;
// a[0] = 0;
// }
// int b[MAXN];
// inline void Ln (int *a,int n)
// {
// memset (b,0,sizeof (b));
// Solve (n,a,b);
// deravitive (a,n);
// while (limit <= n) limit <<= 1,l ++;
// for (Int i = 0; i < limit; ++ i) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
// NTT (a,1),NTT (b,1);
// for (Int i = 0; i < limit; ++ i) a[i] = 1ll * a[i] * b[i] % mod;
// NTT (a,-1),inter (a,n);
// for (Int i = n + 1; i < limit; ++ i) a[i] = 0;
// }
// int F0[MAXN];
// inline void Exp (int *a,int *B,int n)
// {
// if (n == 1) return B[0] = 1,void ();
// Exp (a,B,(n + 1) >> 1);
// for (Int i = 0; i < limit; ++ i) F0[i] = B[i];
// Ln (F0,n);
// F0[0] = (a[0] + 1 + mod - F0[0]) % mod;
// for (Int i = 1; i < n; ++ i) F0[i] = (a[i] + mod - F0[i]) % mod;
// NTT (F0,1);
// NTT (B,1);
// for (Int i = 0; i < limit; ++ i) B[i] = 1ll * F0[i] * B[i] % mod;
// NTT (B,-1);
// for (Int i = n; i < limit; ++ i) B[i] = 0;
// }
// inline int read ()
// {
// int x = 0;
// char c = getchar();
// int f = 1;
// while (c < '0' || c > '9')
// {
// if (c == '-') f = -f;
// c = getchar();
// }
// while (c >= '0' && c <= '9')
// {
// x = (x << 3) + (x << 1) + c - '0';
// c = getchar();
// }
// return x * f;
// }
// inline void write (int x)
// {
// if (x < 0)
// {
// x = -x;
// putchar ('-');
// }
// if (x > 9) write (x / 10);
// putchar (x % 10 + '0');
// }
// int fac[MAXN],caf[MAXN], lim = 512;
// inline void init ()
// {
// fac[0] = 1;
// memset(mp, -1, sizeof(mp));
// for (Int i = 1; i <= lim; ++ i) fac[i] = 1ll * fac[i - 1] * i % mod;
// caf[lim] = quick_pow (fac[lim],mod - 2);
// for (Int i = lim; i; -- i) caf[i - 1] = 1ll * caf[i] * i % mod;
// }
// int H[MAXN],H_[MAXN],G[MAXN],FG[MAXN],SG[MAXN];
// inline void makerev (int len)
// {
// limit = 1,l = 0;
// while (limit < len) limit <<= 1,l ++;
// for (Int i = 0; i < limit; ++ i) r[i] = (r[i >> 1] >> 1) | ((i & 1) << l - 1);
// }
// inline void prepare ()
// {
// int len = 1 << 9;
// makerev (len);
// for (Int i = 0; i < len; ++ i) H[i] = 1ll * quick_pow (2,1ll * i * (i - 1) / 2 % (mod - 1)) * caf[i] % mod;
// Ln (H,len - 1);
// for (Int i = 0; i < len; ++ i) H[i] = H_[i] = 1ll * H[i] * i % mod;
// deravitive (H_,len - 1),makerev (len << 1),NTT (H_,1);
// }
// inline int work (int n)
// {
// int len = 1 << 9;
// memset (SG,0,sizeof (SG)),memset (F0,0,sizeof (F0));
// for (Int i = 0; i < len; ++ i) G[i] = 1ll * H[i] * (mod - n) % mod;
// Exp (G,SG,len),makerev (len << 1),NTT (SG,1);
// for (Int i = 0; i < len << 1; ++ i) SG[i] = 1ll * SG[i] * H_[i] % mod;
// NTT (SG,-1);
// return 1ll * SG[n - 1] * quick_pow (n,mod - 2) % mod * fac[n - 1] % mod;
// }
int mp[401] = {-1, 1, 0, 1, 10, 253, 11968, 1047613, 169181040, 107252390, 786518993, 583438588, 190932423, 405584283, 313694335, 250276001, 606489500, 855839107, 795942812, 338292147, 989295396, 827831283, 879973965, 955037665, 186469564, 402814809, 974258670, 960202991, 560957725, 835930389, 270145319, 607436639, 844195859, 848808224, 498875379, 289724143, 933177440, 843559378, 388782613, 385657974, 305097263, 679756175, 175329675, 341282158, 112818894, 252193495, 19551874, 118522292, 423636711, 772362801, 4215329, 845401535, 773351960, 73279131, 287896918, 35629464, 420273184, 534844639, 850246214, 835403703, 416814380, 969598408, 99821637, 565469638, 435635187, 516664984, 29689827, 37743741, 831033245, 743946237, 986167823, 445024478, 98443289, 210625370, 790898139, 537267550, 908910868, 517062868, 690446239, 817063109, 566120899, 196910261, 330701190, 741275921, 697465590, 51570432, 29560297, 767613443, 548778485, 725609775, 284260441, 592540488, 81388297, 258671035, 432873562, 209057054, 689901211, 116058313, 692874751, 333098827, 833649895, 958497471, 419040170, 284694038, 470421608, 621438024, 308011491, 557480795, 41511832, 177729628, 371071052, 246030132, 12002056, 771737713, 843209588, 99212632, 651188496, 957622590, 928230059, 44136960, 624989121, 956541315, 151562674, 595914133, 172805878, 115038304, 987325878, 790888708, 947709697, 488851492, 264201775, 70593758, 37984785, 973267237, 432274746, 636818254, 501062474, 31896055, 849465426, 425895838, 32937411, 296795779, 892313510, 732976959, 474277441, 949056547, 661261145, 840293422, 216254329, 604445379, 117030186, 944777760, 804587132, 903109211, 746174776, 160804730, 858039744, 366020443, 362904725, 501065036, 271424569, 969041951, 456281902, 252908087, 709234093, 316560499, 612949502, 871740290, 881022917, 549512505, 352839334, 714712068, 215762566, 566984681, 89100523, 246452752, 777454887, 613131924, 473967709, 207898822, 115435047, 120828092, 420656011, 554388114, 813637077, 512162684, 727940787, 42550739, 256948471, 592441014, 783324998, 653428942, 879372011, 244011843, 504953138, 349644725, 437708198, 52821380, 578655603, 760672840, 722392063, 413767583, 806480210, 421486357, 513751913, 344075783, 914211727, 669322126, 672129440, 817804430, 604818176, 680689275, 26543361, 282618663, 558545054, 331753222, 760046111, 599137753, 857285879, 209522628, 254750241, 263392566, 102202572, 724591677, 535325950, 573033420, 538111346, 519486361, 428577166, 785938124, 677290822, 284082092, 185994414, 177574340, 162542487, 507302020, 779343889, 13843679, 523995581, 268826156, 635163989, 211604806, 114549121, 275399163, 764457490, 538612871, 390039499, 908600625, 288398763, 689053026, 511894736, 513643954, 593154822, 338791174, 142568578, 320257756, 568788568, 411603206, 434136307, 915489438, 263224310, 322767624, 614541410, 398969490, 724997592, 995271149, 71771149, 33335273, 265327279, 113217521, 220163712, 100571832, 679386918, 790739720, 210907638, 154633409, 577297755, 463219776, 575652746, 456491730, 328973244, 799289316, 318149878, 981504818, 391235395, 521947457, 660277445, 700060000, 472478682, 165202890, 768398589, 52030275, 72733149, 246525900, 654889447, 266258161, 466175886, 815119137, 978544797, 762707469, 678774440, 128204278, 70568053, 686202353, 120937945, 451614303, 254699044, 4814976, 411949753, 230055208, 97859600, 418414349, 441295246, 788087603, 877023684, 331435490, 916705754, 757595253, 557642302, 84253121, 638630860, 658101906, 838357821, 161232722, 856918288, 834313529, 398186083, 775213077, 407657641, 373212861, 715082522, 403598984, 369506396, 756622736, 459889008, 606748068, 229473391, 678381330, 260556269, 497027689, 784972230, 766954104, 950845234, 381599213, 827210541, 112402327, 92962066, 349545952, 398283942, 534421108, 405423668, 582291746, 823801850, 113039356, 982725387, 29025900, 801058427, 823650572, 346592621, 299267625, 953156651, 580739203, 472093454, 472985388, 819056574, 789340503, 245849586, 613707503, 791150099, 714797175, 588916171, 828419867, 418139064, 85917379, 153892665, 401191822, 34060782, 193364047, 612982617, 526388119, 403932739, 463469628, 462978276, 175904113, 208291256, 855653102, 325839583, 54342864, 478298286, 516310448, 132018656, 258135548, 975226982, 940352583, 546202442, 594737170, 367500375, 557647531, 526064195, 118470447, 410907796};
mint cal(int n) {
return mp[n];
}
}go;
mint fac[maxn];
void solve(){
int n;
std::cin >> n;
// std::cerr << go.cal(1) << " " << go.cal(2) << " " << go.cal(3) << " " << go.cal(4) << "\n";
std::vector<int> a(n);
f[0][0] = 1;
choose[0][0] = 1;
fac[0] = 1;
for (int i = 1; i <= n; i += 1) {
choose[i][0] = 1;
fac[i] = fac[i - 1] * mint(i);
for (int j = 1; j <= i; j += 1) {
choose[i][j] = choose[i - 1][j] + choose[i - 1][j - 1];
}
}
g[0] = 1;
for (auto &x : a) {
std::cin >> x;
memset(new_g, 0, sizeof(new_g));
for (int i = 0; i <= n; i += 1) {
new_g[i] += g[i];
new_g[i + 1] += g[i] * mint(x);
}
memcpy(g, new_g, sizeof(g));
}
// ff[0] = 1;
// for (int i = 1; i <= n; i += 1) {
// ff[i] = power(mint(2), i * (i - 1) / 2);
// for (int j = 1; j < i; j += 1) {
// ff[i] -= ff[j] * choose[i - 1][j - 1] * power(mint(2), (i - j) * (i - j - 1) / 2);
// }
// }
// for (int i = 1; i <= n; i += 1) {
// f[i][0] = ff[i];
// for (int j = 1; j <= i; j += 1) {
// for (int k = 1; k < i; k += 1) {
// f[i][j] += f[i - k][j - 1] * f[k][0] * (i - k) * k * choose[i - 1][k - 1];
// }
// f[i][0] -= f[i][j];
// }
// }
dp[1][1] = 1;
for (int i = 2; i <= n; i += 1) {
memset(new_dp, 0, sizeof(new_dp));
for (int j = 1; j <= i; j += 1) {
for (int k = 1; k <= i; k += 1) {
new_dp[j][k + 1] += dp[j][k];
// new_dp[j + 1][1] += dp[j][k] * k * f[k][0];
new_dp[j + 1][1] += dp[j][k] * mint(k) * go.cal(k) / (fac[k - 1]);
}
}
memcpy(dp, new_dp, sizeof(dp));
}
mint res = 0;
for (int i = 1; i <= n; i += 1) {
for (int j = 1; j <= n; j += 1) {
mint cur = dp[i][j] * go.cal(j) * g[i] / (fac[j - 1]) * fac[n - i];
if (i > 1) {
cur *= mint(j) * power(mint(n), i - 2);
}
res += cur;
// std::cerr << i << " " << j << " " << dp[i][j] << " " << g[i + 1] << " " << res << "\n";
}
}
std::cout << res << '\n';
}
int main(){
// go.init();
// go.prepare();
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 6376kb
input:
3 8 5 9
output:
1102
result:
ok "1102"
Test #2:
score: 0
Accepted
time: 2ms
memory: 6184kb
input:
5 4 2 1 3 10
output:
63860
result:
ok "63860"
Test #3:
score: 0
Accepted
time: 0ms
memory: 6408kb
input:
7 229520041 118275986 281963154 784360383 478705114 655222915 970715006
output:
35376232
result:
ok "35376232"
Test #4:
score: 0
Accepted
time: 1207ms
memory: 6096kb
input:
300 7 8 2 8 6 5 5 3 2 3 8 0 6 0 1 0 10 7 10 0 1 0 6 7 2 6 4 7 9 4 6 5 5 9 8 5 4 5 3 5 4 4 10 2 4 9 7 5 2 2 5 6 3 6 8 2 8 3 6 2 5 1 10 3 0 7 1 9 6 5 10 0 3 0 2 4 2 7 6 10 1 0 0 9 4 3 5 5 2 6 1 8 5 4 0 0 5 8 8 1 3 9 9 9 8 1 4 10 7 4 8 5 0 4 3 4 4 8 1 6 1 10 9 3 2 5 0 0 5 2 7 5 4 10 3 5 10 10 7 6 10 3 ...
output:
409590176
result:
ok "409590176"
Test #5:
score: 0
Accepted
time: 1672ms
memory: 6180kb
input:
335 4 3 7 7 8 1 4 7 8 8 4 3 5 5 6 8 8 9 3 7 2 4 6 6 6 3 0 7 8 4 6 1 9 10 9 9 0 7 10 3 3 4 10 5 10 4 10 3 7 7 1 9 8 4 0 3 8 1 10 10 7 5 2 7 6 0 4 7 5 9 1 4 10 3 2 9 2 0 1 5 3 5 5 9 9 3 5 6 10 6 9 5 10 10 8 10 5 9 6 1 10 6 7 1 0 7 10 1 6 7 8 2 2 10 1 3 4 1 5 3 3 2 4 10 3 5 8 0 10 0 9 4 9 2 7 3 8 7 4 7...
output:
997747
result:
ok "997747"
Test #6:
score: 0
Accepted
time: 32ms
memory: 6440kb
input:
84 2 5 3 4 5 8 10 5 2 10 7 6 10 10 7 7 3 2 1 7 8 5 9 10 7 5 6 1 2 8 2 8 6 5 4 6 9 0 3 9 3 2 0 2 9 0 4 4 8 10 3 4 6 10 10 5 8 1 10 8 2 7 3 10 8 8 3 2 8 7 4 10 2 6 9 9 3 6 3 3 9 0 7 6
output:
182929290
result:
ok "182929290"
Test #7:
score: 0
Accepted
time: 11ms
memory: 6208kb
input:
54 9 2 1 10 6 6 10 4 7 6 0 3 8 10 5 7 8 6 1 10 9 6 1 8 0 4 2 7 4 0 9 8 5 3 0 4 3 6 1 8 4 1 4 9 6 6 8 0 8 0 0 7 6 9
output:
43066240
result:
ok "43066240"
Test #8:
score: 0
Accepted
time: 2ms
memory: 6444kb
input:
32 0 8 6 8 1 3 9 5 9 0 4 2 4 4 3 10 2 3 1 8 2 6 5 3 9 5 0 0 5 2 1 4
output:
718335570
result:
ok "718335570"
Test #9:
score: 0
Accepted
time: 2ms
memory: 6244kb
input:
1 998244352
output:
998244352
result:
ok "998244352"
Test #10:
score: -100
Time Limit Exceeded
input:
400 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244...