QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#245097#7634. CardsKNU_0_GB_RAM (Vladyslav Zavodnyk, Kostiantyn Lutsenko, Kostiantyn Savchuk)#AC ✓12087ms28420kbC++203.1kb2023-11-09 18:41:332023-11-09 18:41:33

Judging History

This is the latest submission verdict.

  • [2023-11-09 18:41:33]
  • Judged
  • Verdict: AC
  • Time: 12087ms
  • Memory: 28420kb
  • [2023-11-09 18:41:33]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define sz(x) (int)(x).size()
typedef vector<int> vi;
const ll mod = 998244353, root = 62;

ll modpow(ll b, ll e) {
    ll ans = 1;
    for (; e; b = b * b % mod, e /= 2)
        if (e & 1) ans = ans * b % mod;
    return ans;
}

typedef vector<ll> vl;
void ntt(vl &a) {
    int n = sz(a), L = 31 - __builtin_clz(n);
    static vl rt(2, 1);
    for (static int k = 2, s = 2; k < n; k *= 2, s++) {
        rt.resize(n);
        ll z[] = {1, modpow(root, mod >> s)};
        rep(i,k,2*k) rt[i] = rt[i / 2] * z[i & 1] % mod;
    }
    vi rev(n);
    rep(i,0,n) rev[i] = (rev[i / 2] | (i & 1) << L) / 2;
    rep(i,0,n) if (i < rev[i]) swap(a[i], a[rev[i]]);
    for (int k = 1; k < n; k *= 2)
        for(int i = 0; i < n; i += 2*k) rep(j,0,k) {
            ll z = rt[j + k] * a[i + j + k] % mod, &ai = a[i + j];
            a[i + j + k] = ai - z + (z > ai ? mod : 0);
            ai += (ai + z >= mod ? z - mod : z);
        }
}

vl conv(const vl &a, const vl &b) {
    if (a.empty() || b.empty()) return {};
    int s = sz(a) + sz(b) - 1, B = 32 - __builtin_clz(s), n = 1<<B;
    int inv = modpow(n, mod - 2);
    vl L(a), R(b), out(n);
    L.resize(n); R.resize(n);
    ntt(L), ntt(R);
    rep(i,0,n) out[-i & (n-1)] = (ll)L[i] * R[i] % mod * inv % mod;
    ntt(out);
    return {out.begin(), out.begin() + s};
}

const int N = 303303, C = 2000;
int n, m, dp[N], tmp[4 * C + 5];
ll p[5];

vl get_trans(int x) {
    vl trans {1}, base(p, p + 5);
    while(x) {
        if(x & 1) trans = conv(trans, base);
        base = conv(base, base);
        x >>= 1;
    }
    return trans;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    int s = 0;
    for(auto &i : p) cin >> i, s = (s + i) % mod;
    int is = modpow(s, mod - 2);
    for(auto &i : p) i = i * 1ll * is % mod;

    dp[n] = 1;
    n = n + 2 * m;
    vl trans = get_trans(C);
    for(int i = 0; i < m;) {
        int step = min(m - i, C);
        i += step;
        if(step != C) trans = get_trans(step);

        vl top(n - 2 * step + 1);
        for(int i = 2 * step; i <= n; i++)
            top[i - 2 * step] = dp[i], dp[i] = 0;
        
        for(int it = step; it--;) {
            memset(tmp, 0, sizeof tmp);
            for(int i = 0; i < 4 * step; i++) {
                for(int j = (i < 2) + (i < 1); j < 5; j++) {
                    // cout << i << " " << i + j - 2 << " " << dp[i] * 1ll * p[j] % mod <<endl;
                    tmp[i + j - 2] = (tmp[i + j - 2] + dp[i] * 1ll * p[j]) % mod;
                }
            }
            memmove(dp, tmp, 4 * step * sizeof(int));
        }

        top = conv(top, trans);

        for(int i = 0; i <= n; i++) {
            // cout << i << " == " << dp[i] << " " << top[i] << endl;
            dp[i] = dp[i] + top[i] >= mod ? dp[i] + top[i] - mod : dp[i] + top[i];
        }
    }
    ll sum = 0;
    for(auto &i : dp) {sum += i;}
    cout << sum % mod << '\n';
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 8ms
memory: 3932kb

input:

1 1
1 1 1 1 1

output:

399297742

result:

ok 1 number(s): "399297742"

Test #2:

score: 0
Accepted
time: 11575ms
memory: 28032kb

input:

100000 100000
1234 4567 7890 4321 54321

output:

348074135

result:

ok 1 number(s): "348074135"

Test #3:

score: 0
Accepted
time: 12087ms
memory: 28112kb

input:

100000 100000
1 2 3 4 5

output:

639188342

result:

ok 1 number(s): "639188342"

Test #4:

score: 0
Accepted
time: 11539ms
memory: 28128kb

input:

100000 100000
5 4 3 2 1

output:

211669278

result:

ok 1 number(s): "211669278"

Test #5:

score: 0
Accepted
time: 8ms
memory: 3936kb

input:

0 0
1 1 1 1 1

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: 0
Accepted
time: 3654ms
memory: 10128kb

input:

1 50000
1 1 1 1 1

output:

548880636

result:

ok 1 number(s): "548880636"

Test #7:

score: 0
Accepted
time: 14ms
memory: 6036kb

input:

50000 1
1 1 1 1 1

output:

1

result:

ok 1 number(s): "1"

Test #8:

score: 0
Accepted
time: 11580ms
memory: 28132kb

input:

100000 100000
234 666 7655 12234 0

output:

45268602

result:

ok 1 number(s): "45268602"

Test #9:

score: 0
Accepted
time: 11572ms
memory: 28412kb

input:

99999 99999
12345 54332 12345 65432 34444

output:

360543661

result:

ok 1 number(s): "360543661"

Test #10:

score: 0
Accepted
time: 11842ms
memory: 28420kb

input:

99998 99998
1 1 1 1 1

output:

602326230

result:

ok 1 number(s): "602326230"

Test #11:

score: 0
Accepted
time: 11604ms
memory: 27852kb

input:

99998 99997
1 1 1 1 1

output:

159752985

result:

ok 1 number(s): "159752985"

Test #12:

score: 0
Accepted
time: 11596ms
memory: 28052kb

input:

99997 100000
1 2 3 4 5

output:

139603712

result:

ok 1 number(s): "139603712"

Test #13:

score: 0
Accepted
time: 11745ms
memory: 27920kb

input:

100000 99997
1 2 2 1 3232323

output:

363030953

result:

ok 1 number(s): "363030953"

Test #14:

score: 0
Accepted
time: 3ms
memory: 4196kb

input:

0 0
0 0 1 0 0

output:

1

result:

ok 1 number(s): "1"

Test #15:

score: 0
Accepted
time: 674ms
memory: 6196kb

input:

10000 10000
91095828 93770094 5303328 491263 50290308

output:

135900098

result:

ok 1 number(s): "135900098"

Test #16:

score: 0
Accepted
time: 684ms
memory: 6500kb

input:

9226 9995
62366139 253808 1929312 491263 4375669

output:

812662634

result:

ok 1 number(s): "812662634"

Test #17:

score: 0
Accepted
time: 673ms
memory: 6364kb

input:

18641 10000
1061 4359 1330 13764 16043

output:

112339046

result:

ok 1 number(s): "112339046"

Extra Test:

score: 0
Extra Test Passed