QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#230033#7634. Cardsucup-team1198#AC ✓1959ms27228kbC++205.1kb2023-10-28 17:27:552023-10-28 19:29:26

Judging History

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

  • [2023-10-28 19:29:26]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:1959ms
  • 内存:27228kb
  • [2023-10-28 17:27:56]
  • 评测
  • 测评结果:100
  • 用时:1952ms
  • 内存:27252kb
  • [2023-10-28 17:27:55]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define pii pair<int, int>
#define ld long double
#define all(a) (a).begin(), (a).end()

const int MOD = 998244353;

int add(int a, int b) {
    return a + b >= MOD ? a + b - MOD : a + b;
}

int sub(int a, int b) {
    return a >= b ? a - b : a + MOD - b;
}

int mul(int a, int b) {
    return (1ll * a * b) % MOD;
}

int pw(int x, int n) {
    int res = 1;
    while (n) {
        if (n % 2 == 0) {
            x = mul(x, x);
            n /= 2;
        } else {
            res = mul(res, x);
            n--;
        }
    }
    return res;
}

const int G = 3;

void fft(vector<int>& a, bool inv = false) {
    int n = a.size();
    int k = 0;
    while ((1 << k) < n) ++k;
    static vector<int> rev, power = {0, 1};
    rev.resize(n);
    rev[0] = 0;
    for (int i = 1; i < n; ++i) {
        rev[i] = rev[i / 2] / 2 + ((i & 1) << (k - 1));
        if (i < rev[i]) {
            swap(a[i], a[rev[i]]);
        }
    }
    for (int l = 1; l < n; l *= 2) {
        if ((int)power.size() == l) {
            power.resize(2 * l);
            int w = pw(G, (MOD - 1) / 2 / l);
            for (int i = l; i < 2 * l; ++i) {
                power[i] = power[i / 2];
                if (i & 1) {
                    power[i] = mul(power[i], w);
                }
            }
        }
        for (int i = 0; i < n; i += 2 * l) {
            for (int j = 0; j < l; ++j) {
                int x = a[i + j], y = mul(a[i + j + l], power[j + l]);
                a[i + j] = add(x, y);
                a[i + j + l] = sub(x, y);
            }
        }
    }
    if (inv) {
        int anti = pw(n, MOD - 2);
        for (int i = 0; i < n; ++i) {
            a[i] = mul(a[i], anti);
        }
        reverse(a.begin() + 1, a.end());
    }
}

vector<int> operator*(vector<int> a, vector<int> b) {
    int sz = a.size() + b.size() - 1;
    int k = 0;
    while ((1 << k) < sz) ++k;
    a.resize(1 << k);
    b.resize(1 << k);
    fft(a);
    fft(b);
    for (int i = 0; i < (1 << k); ++i) {
        a[i] = mul(a[i], b[i]);
    }
    fft(a, true);
    a.resize(sz);
    return a;
}

const int MAXN = 2e5 + 100;
vector<int> powers[MAXN];

int sum = 0;

void calc_powers(int len, const vector<int>& a) {
    /// cerr << len << endl;
    if (!powers[len].empty()) return;
    if (len == 0) {
        powers[len] = {1};
        return;
    }
    if (len == 1) {
        powers[len] = a;
        sum += a.size();
        return;
    }
    calc_powers(len / 2, a);
    calc_powers((len + 1) / 2, a);
    powers[len] = powers[len / 2] * powers[(len + 1) / 2];
    sum += powers[len].size();
}

vector<int> operator+(const vector<int>& a, const vector<int>& b) {
    vector<int> c(max(a.size(), b.size()));
    for (int i = 0; i < (int)a.size(); ++i) {
        c[i] = add(c[i], a[i]);
    }
    for (int i = 0; i < (int)b.size(); ++i) {
        c[i] = add(c[i], b[i]);
    }
    return c;
}

vector<int> solve(int len, vector<int> cur) {
    if (len == 1) {
        auto res = cur * powers[1];
        for (int i = 2; i < (int)res.size(); ++i) {
            res[i - 2] = res[i];
        }
        res.pop_back();
        res.pop_back();
        return res;
    }
    int len1 = len / 2;
    int len2 = (len + 1) / 2;
    vector<int> to_add = {0};
    if ((int)cur.size() > 2 * len1) {
        to_add.resize(cur.size() - 2 * len1);
        for (int i = 0; i < (int)to_add.size(); ++i) {
            to_add[i] = cur[i + 2 * len1];
        }
        to_add = to_add * powers[len1];
        cur.resize(2 * len1);
    }
    cur = solve(len1, cur) + to_add;
    to_add = {0};
    if ((int)cur.size() > 2 * len2) {
        to_add.resize(cur.size() - 2 * len2);
        for (int i = 0; i < (int)to_add.size(); ++i) {
            to_add[i] = cur[i + 2 * len2];
        }
        to_add = to_add * powers[len2];
        cur.resize(2 * len2);
    }
    cur = solve(len2, cur) + to_add;
    return cur;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<int> p(5);
    int sum = 0;
    for (int i = 0; i < 5; ++i) {
        cin >> p[i];
        sum += p[i];
    }
    if (m == 0) {
        cout << "1\n";
        return 0;
    }
    sum = pw(sum, MOD - 2);
    for (int i = 0; i < 5; ++i) {
        p[i] = mul(p[i], sum);
    }

    /**vector<int> slow(n + 1);
    slow[n] = 1;
    for (int i = 0; i < m; ++i) {
        vector<int> slow2(slow.size() + 2);
        for (int i = 0; i < (int)slow.size(); ++i) {
            for (int j = 0; j < 5; ++j) {
                if (i + j - 2 < 0) continue;
                slow2[i + j - 2] = add(slow2[i + j - 2], mul(slow[i], p[j]));
            }
        }
        slow = move(slow2);
    }
    int ans_slow = 0;
    for (int i = 0; i < (int)slow.size(); ++i) {
        ans_slow = add(ans_slow, slow[i]);
    }
    cout << ans_slow << "\n";*/

    /// cout << (1 << 17) - 1 << endl;
    calc_powers(m, p);
    /// cerr << ::sum << endl;
    vector<int> start(n + 1);
    start[n] = 1;
    auto res = solve(m, start);
    int ans = 0;
    for (int i = 0; i < (int)res.size(); ++i) {
        ans = add(ans, res[i]);
    }
    cout << ans << "\n";
    return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 8284kb

input:

1 1
1 1 1 1 1

output:

399297742

result:

ok 1 number(s): "399297742"

Test #2:

score: 0
Accepted
time: 1871ms
memory: 23880kb

input:

100000 100000
1234 4567 7890 4321 54321

output:

348074135

result:

ok 1 number(s): "348074135"

Test #3:

score: 0
Accepted
time: 1851ms
memory: 23792kb

input:

100000 100000
1 2 3 4 5

output:

639188342

result:

ok 1 number(s): "639188342"

Test #4:

score: 0
Accepted
time: 1862ms
memory: 23872kb

input:

100000 100000
5 4 3 2 1

output:

211669278

result:

ok 1 number(s): "211669278"

Test #5:

score: 0
Accepted
time: 2ms
memory: 8336kb

input:

0 0
1 1 1 1 1

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: 0
Accepted
time: 922ms
memory: 15356kb

input:

1 50000
1 1 1 1 1

output:

548880636

result:

ok 1 number(s): "548880636"

Test #7:

score: 0
Accepted
time: 4ms
memory: 9332kb

input:

50000 1
1 1 1 1 1

output:

1

result:

ok 1 number(s): "1"

Test #8:

score: 0
Accepted
time: 1837ms
memory: 23808kb

input:

100000 100000
234 666 7655 12234 0

output:

45268602

result:

ok 1 number(s): "45268602"

Test #9:

score: 0
Accepted
time: 1956ms
memory: 27228kb

input:

99999 99999
12345 54332 12345 65432 34444

output:

360543661

result:

ok 1 number(s): "360543661"

Test #10:

score: 0
Accepted
time: 1896ms
memory: 25632kb

input:

99998 99998
1 1 1 1 1

output:

602326230

result:

ok 1 number(s): "602326230"

Test #11:

score: 0
Accepted
time: 1959ms
memory: 26984kb

input:

99998 99997
1 1 1 1 1

output:

159752985

result:

ok 1 number(s): "159752985"

Test #12:

score: 0
Accepted
time: 1882ms
memory: 24408kb

input:

99997 100000
1 2 3 4 5

output:

139603712

result:

ok 1 number(s): "139603712"

Test #13:

score: 0
Accepted
time: 1951ms
memory: 27004kb

input:

100000 99997
1 2 2 1 3232323

output:

363030953

result:

ok 1 number(s): "363030953"

Test #14:

score: 0
Accepted
time: 0ms
memory: 8496kb

input:

0 0
0 0 1 0 0

output:

1

result:

ok 1 number(s): "1"

Test #15:

score: 0
Accepted
time: 127ms
memory: 9592kb

input:

10000 10000
91095828 93770094 5303328 491263 50290308

output:

135900098

result:

ok 1 number(s): "135900098"

Test #16:

score: 0
Accepted
time: 145ms
memory: 9908kb

input:

9226 9995
62366139 253808 1929312 491263 4375669

output:

812662634

result:

ok 1 number(s): "812662634"

Test #17:

score: 0
Accepted
time: 117ms
memory: 9996kb

input:

18641 10000
1061 4359 1330 13764 16043

output:

112339046

result:

ok 1 number(s): "112339046"

Extra Test:

score: 0
Extra Test Passed