QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#230448#7634. Cardsucup-team1191#AC ✓2914ms24780kbC++206.3kb2023-10-28 18:47:472023-10-28 19:30:11

Judging History

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

  • [2023-10-28 19:30:11]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:2914ms
  • 内存:24780kb
  • [2023-10-28 18:47:47]
  • 评测
  • 测评结果:100
  • 用时:2964ms
  • 内存:24744kb
  • [2023-10-28 18:47:47]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
#define TIME (clock() * 1.0 / CLOCKS_PER_SEC)

// если модуль подается на вход, убрать все <> и раскомментировать нужные строки
using uint = unsigned int;
using ull = unsigned long long;
template <uint MD> struct ModInt {
    using M = ModInt;
    // static int MD;
    uint v;
    ModInt(ll _v = 0) { set_v(uint(_v % MD + MD)); }
    M& set_v(uint _v) {
        v = (_v < MD) ? _v : _v - MD;
        return *this;
    }
    explicit operator bool() const { return v != 0; }
    M operator-() const { return M() - *this; }
    M operator+(const M& r) const { return M().set_v(v + r.v); }
    M operator-(const M& r) const { return M().set_v(v + MD - r.v); }
    M operator*(const M& r) const { return M().set_v(uint((ull)v * r.v % MD)); }
    M operator/(const M& r) const { return *this * r.inv(); }
    M& operator+=(const M& r) { return *this = *this + r; }
    M& operator-=(const M& r) { return *this = *this - r; }
    M& operator*=(const M& r) { return *this = *this * r; }
    M& operator/=(const M& r) { return *this = *this / r; }
    bool operator==(const M& r) const { return v == r.v; }
    bool operator!=(const M& r) const { return v != r.v; }
    M inv() const;
    friend istream& operator>>(istream& is, M& r) { ll x; is >> x; r = M(x); return is; }
    friend ostream& operator<<(ostream& os, const M& r) { return os << r.v; }
};

template<uint MD>
ModInt<MD> pow(ModInt<MD> x, ll n) {
    ModInt<MD> r = 1;
    while (n) {
        if (n & 1) r *= x;
        x *= x;
        n >>= 1;
    }
    return r;
}

template<uint MD>
ModInt<MD> ModInt<MD>::inv() const { return pow(*this, MD - 2); }
// or copy egcd and {return egcd(MD, v, 1).second;}

// if MD is from input
// this line is necessary, read later as you wish
// int ModInt::MD;

const int MOD = 998'244'353;
using Mint = ModInt<MOD>;
// using Mint = double;

#define V vector
void nft(bool type, V<Mint>& a) {
    Mint G = 3;
    int n = int(a.size()), s = 0;
    while ((1 << s) < n) s++;
    assert(1 << s == n);

    static V<Mint> ep, iep;
    while (int(ep.size()) <= s) {
        ep.push_back(pow(G, Mint(-1).v / (1 << ep.size())));
        iep.push_back(ep.back().inv());
    }
    V<Mint> b(n);
    for (int i = 1; i <= s; i++) {
        int w = 1 << (s - i);
        Mint base = type ? iep[i] : ep[i], now = 1;
        for (int y = 0; y < n / 2; y += w) {
            for (int x = 0; x < w; x++) {
                auto l = a[y << 1 | x];
                auto r = now * a[y << 1 | x | w];
                b[y | x] = l + r;
                b[y | x | n >> 1] = l - r;
            }
            now *= base;
        }
        swap(a, b);
    }
}

V<Mint> multiply_nft(const V<Mint>& a, const V<Mint>& b) {
    int n = int(a.size()), m = int(b.size());
    if (!n || !m) return {};
    if (min(n, m) <= 50) {
        V<Mint> ans(n + m - 1);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) ans[i + j] += a[i] * b[j];
        return ans;
    }
    int lg = 0;
    while ((1 << lg) < n + m - 1) lg++;
    int z = 1 << lg;
    auto a2 = a, b2 = b;
    a2.resize(z);
    b2.resize(z);
    nft(false, a2);
    nft(false, b2);
    for (int i = 0; i < z; i++) a2[i] *= b2[i];
    nft(true, a2);
    a2.resize(n + m - 1);
    Mint iz = Mint(z).inv();
    for (int i = 0; i < n + m - 1; i++) a2[i] *= iz;
    return a2;
}

struct rval {
    vector<Mint> values;
};

const int M = 1e5 + 239;

vector<Mint> base;

vector<Mint> pw[M];

void obtain(int s) {
    if (!pw[s].empty()) {
        return;
    }
    obtain(s / 2);
    obtain((s + 1) / 2);
    pw[s] = multiply_nft(pw[s / 2], pw[(s + 1) / 2]);
}

vector<Mint> func(int x1, int y1, int x2, int y2, vector<Mint>& val) {
    vector<Mint> ans(y2 + 1, 0);
    if (x2 == x1 + 1) {
        for (int y = 0; y <= y2; y++) {
            for (int dy = -2; dy <= 2; dy++) {
                if (y + dy >= 0 && y + dy <= y1) {
                    ans[y] += val[y + dy] * base[2 - dy];
                }
            }
        }
        return ans;
    }
    int len = (x2 - x1);
    if (y2 >= 2 * len) {
        obtain(len);
        auto res = multiply_nft(val, pw[len]);
        for (int i = 2 * len; i <= y2; i++) {
            if (i + 2 * len < (int)res.size()) {
                ans[i] = res[i + 2 * len];
            }
        }
    }
    int mid = (x1 + x2) / 2;

    int r_len = min(y2, 2 * len - 1);
    int mid_len = r_len + 2 * (x2 - mid);
    int l_len = min(y1, mid_len + 2 * (mid - x1));
    val.resize(l_len + 1);

    auto midvals = func(x1, l_len, mid, mid_len, val);
    auto rvals = func(mid, mid_len, x2, r_len, midvals);
    for (int i = 0; i <= r_len; i++) {
        ans[i] = rvals[i];
    }

    return ans;
}

Mint slow(int n, int m) {
    vector<Mint> dp(n + 2 * m + 1, 0);
    dp[n] = 1;
    for (int it = 0; it < m; it++) {
        vector<Mint> new_dp(dp.size(), 0);
        for (int y = 0; y < (int)dp.size(); y++) {
            for (int dy = -2; dy <= 2; dy++) {
                if (y + dy >= 0 && y + dy < (int)new_dp.size()) {
                    new_dp[y + dy] += dp[y] * base[2 + dy];
                }
            }
        }
        swap(dp, new_dp);
    }
    Mint ans = 0;
    for (const auto& t : dp) {
        ans += t;
    }
    return ans;
}

void solve() {
    int n, m;
    cin >> n >> m;

    if (m == 0) {
        cout << "1\n";
        return;
    }

    base.resize(5);
    Mint s = 0;
    for (int i = 0; i < 5; i++) {
        cin >> base[i];
        s += base[i];
    }
    for (int i = 0; i < 5; i++) {
        base[i] /= s;
    }

#ifdef ONPC
    if ((ll)(n + 2 * m) * (n + 2 * m) <= 1000000) {
        cout << slow(n, m) << "\n";
    }
#endif

    pw[1] = base;
    vector<Mint> vals(n + 1, 0);
    vals[n] = 1;
    auto res = func(0, n, m, n + 2 * m, vals);
    Mint ans = 0;
    for (const auto& t : res) {
        ans += t;
    }
    cout << ans << "\n";
}

int main() {
#ifdef ONPC
    freopen("input", "r", stdin);
#endif
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }

    cerr << TIME << "\n";

    return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 6328kb

input:

1 1
1 1 1 1 1

output:

399297742

result:

ok 1 number(s): "399297742"

Test #2:

score: 0
Accepted
time: 2801ms
memory: 22420kb

input:

100000 100000
1234 4567 7890 4321 54321

output:

348074135

result:

ok 1 number(s): "348074135"

Test #3:

score: 0
Accepted
time: 2805ms
memory: 22312kb

input:

100000 100000
1 2 3 4 5

output:

639188342

result:

ok 1 number(s): "639188342"

Test #4:

score: 0
Accepted
time: 2801ms
memory: 22248kb

input:

100000 100000
5 4 3 2 1

output:

211669278

result:

ok 1 number(s): "211669278"

Test #5:

score: 0
Accepted
time: 1ms
memory: 6388kb

input:

0 0
1 1 1 1 1

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: 0
Accepted
time: 1304ms
memory: 13364kb

input:

1 50000
1 1 1 1 1

output:

548880636

result:

ok 1 number(s): "548880636"

Test #7:

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

input:

50000 1
1 1 1 1 1

output:

1

result:

ok 1 number(s): "1"

Test #8:

score: 0
Accepted
time: 2765ms
memory: 22296kb

input:

100000 100000
234 666 7655 12234 0

output:

45268602

result:

ok 1 number(s): "45268602"

Test #9:

score: 0
Accepted
time: 2904ms
memory: 24752kb

input:

99999 99999
12345 54332 12345 65432 34444

output:

360543661

result:

ok 1 number(s): "360543661"

Test #10:

score: 0
Accepted
time: 2848ms
memory: 23752kb

input:

99998 99998
1 1 1 1 1

output:

602326230

result:

ok 1 number(s): "602326230"

Test #11:

score: 0
Accepted
time: 2909ms
memory: 24780kb

input:

99998 99997
1 1 1 1 1

output:

159752985

result:

ok 1 number(s): "159752985"

Test #12:

score: 0
Accepted
time: 2835ms
memory: 22240kb

input:

99997 100000
1 2 3 4 5

output:

139603712

result:

ok 1 number(s): "139603712"

Test #13:

score: 0
Accepted
time: 2914ms
memory: 24772kb

input:

100000 99997
1 2 2 1 3232323

output:

363030953

result:

ok 1 number(s): "363030953"

Test #14:

score: 0
Accepted
time: 1ms
memory: 6336kb

input:

0 0
0 0 1 0 0

output:

1

result:

ok 1 number(s): "1"

Test #15:

score: 0
Accepted
time: 172ms
memory: 7368kb

input:

10000 10000
91095828 93770094 5303328 491263 50290308

output:

135900098

result:

ok 1 number(s): "135900098"

Test #16:

score: 0
Accepted
time: 186ms
memory: 7692kb

input:

9226 9995
62366139 253808 1929312 491263 4375669

output:

812662634

result:

ok 1 number(s): "812662634"

Test #17:

score: 0
Accepted
time: 155ms
memory: 7632kb

input:

18641 10000
1061 4359 1330 13764 16043

output:

112339046

result:

ok 1 number(s): "112339046"

Extra Test:

score: 0
Extra Test Passed