QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#316558#8180. Bridge Eliminationucup-team2112#TL 1672ms6444kbC++2014.4kb2024-01-27 21:48:082024-01-27 21:48:09

Judging History

你现在查看的是最新测评结果

  • [2024-01-27 21:48:09]
  • 评测
  • 测评结果:TL
  • 用时:1672ms
  • 内存:6444kb
  • [2024-01-27 21:48:08]
  • 提交

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...

output:


result: