QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#829205#9553. The Hermitucup-team4435#AC ✓18ms4564kbC++2311.5kb2024-12-24 06:57:092024-12-24 06:57:14

Judging History

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

  • [2024-12-24 06:57:14]
  • 评测
  • 测评结果:AC
  • 用时:18ms
  • 内存:4564kb
  • [2024-12-24 06:57:09]
  • 提交

answer

#include "bits/stdc++.h"


#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i < (n); ++i)
#define rep1n(i, n) for (int i = 1; i <= (n); ++i)
#define repr(i, n) for (int i = (n) - 1; i >= 0; --i)
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define each(x, a) for (auto &x : a)
#define ar array
#define vec vector
#define range(i, n) rep(i, n)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using str = string;
using pi = pair<int, int>;
using pl = pair<ll, ll>;

using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector<pair<int, int>>;
using vvi = vector<vi>;

int Bit(int mask, int b) { return (mask >> b) & 1; }

template<class T>
bool ckmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool ckmax(T &a, const T &b) {
    if (b > a) {
        a = b;
        return true;
    }
    return false;
}

// [l, r)
template<typename T, typename F>
T FindFirstTrue(T l, T r, const F &predicat) {
    --l;
    while (r - l > 1) {
        T mid = l + (r - l) / 2;
        if (predicat(mid)) {
            r = mid;
        } else {
            l = mid;
        }
    }
    return r;
}


template<typename T, typename F>
T FindLastFalse(T l, T r, const F &predicat) {
    return FindFirstTrue(l, r, predicat) - 1;
}

const int INFi = 2e9;
const ll INF = 2e18;

/*
 ! WARNING: MOD must be prime if you use division or .inv().
 ! WARNING: 2 * (MOD - 1) must be smaller than INT_MAX
 * Use .value to get the stored value.
 */
template<typename T>
int normalize(T value, int mod) {
    if (value < -mod || value >= 2 * mod) value %= mod;
    if (value < 0) value += mod;
    if (value >= mod) value -= mod;
    return value;
}

template<int mod>
struct static_modular_int {
    static_assert(mod - 2 <= std::numeric_limits<int>::max() - mod, "2(mod - 1) <= INT_MAX");
    using mint = static_modular_int<mod>;

    int value;

    static_modular_int() : value(0) {}
    static_modular_int(const mint &x) : value(x.value) {}

    template<typename T, typename U = std::enable_if_t<std::is_integral<T>::value>>
    static_modular_int(T value) : value(normalize(value, mod)) {}

    static constexpr int get_mod() {
        return mod;
    }

    template<typename T>
    mint power(T degree) const {
        mint prod = 1, a = *this;
        for (; degree > 0; degree >>= 1, a *= a)
            if (degree & 1)
                prod *= a;

        return prod;
    }

    mint inv() const {
        return power(mod - 2);
    }

    mint& operator=(const mint &x) {
        value = x.value;
        return *this;
    }

    mint& operator+=(const mint &x) {
        value += x.value;
        if (value >= mod) value -= mod;
        return *this;
    }

    mint& operator-=(const mint &x) {
        value -= x.value;
        if (value < 0) value += mod;
        return *this;
    }

    mint& operator*=(const mint &x) {
        value = int64_t(value) * x.value % mod;
        return *this;
    }

    mint& operator/=(const mint &x) {
        return *this *= x.inv();
    }

    friend mint operator+(const mint &x, const mint &y) {
        return mint(x) += y;
    }

    friend mint operator-(const mint &x, const mint &y) {
        return mint(x) -= y;
    }

    friend mint operator*(const mint &x, const mint &y) {
        return mint(x) *= y;
    }

    friend mint operator/(const mint &x, const mint &y) {
        return mint(x) /= y;
    }

    mint& operator++() {
        ++value;
        if (value == mod) value = 0;
        return *this;
    }

    mint& operator--() {
        --value;
        if (value == -1) value = mod - 1;
        return *this;
    }

    mint operator++(int) {
        mint prev = *this;
        value++;
        if (value == mod) value = 0;
        return prev;
    }

    mint operator--(int) {
        mint prev = *this;
        value--;
        if (value == -1) value = mod - 1;
        return prev;
    }

    mint operator-() const {
        return mint(0) - *this;
    }

    bool operator==(const mint &x) const {
        return value == x.value;
    }

    bool operator!=(const mint &x) const {
        return value != x.value;
    }

    bool operator<(const mint &x) const {
        return value < x.value;
    }

    template<typename T>
    explicit operator T() {
        return value;
    }

    friend std::istream& operator>>(std::istream &in, mint &x) {
        std::string s;
        in >> s;
        x = 0;
        bool neg = s[0] == '-';
        for (const auto c : s)
            if (c != '-')
                x = x * 10 + (c - '0');

        if (neg)
            x *= -1;

        return in;
    }

    friend std::ostream& operator<<(std::ostream &out, const mint &x) {
        return out << x.value;
    }

    static int primitive_root() {
        if constexpr (mod == 1'000'000'007)
            return 5;
        if constexpr (mod == 998'244'353)
            return 3;
        if constexpr (mod == 786433)
            return 10;

        static int root = -1;
        if (root != -1)
            return root;

        std::vector<int> primes;
        int value = mod - 1;
        for (int i = 2; i * i <= value; i++)
            if (value % i == 0) {
                primes.push_back(i);
                while (value % i == 0)
                    value /= i;
            }

        if (value != 1)
            primes.push_back(value);

        for (int r = 2;; r++) {
            bool ok = true;
            for (auto p : primes)
                if ((mint(r).power((mod - 1) / p)).value == 1) {
                    ok = false;
                    break;
                }

            if (ok)
                return root = r;
        }
    }
};

// constexpr int MOD = 1'000'000'007;
 constexpr int MOD = 998'244'353;
using mint = static_modular_int<MOD>;

/*
 ! WARNING: MOD must be prime.
 * Define modular int class above it.
 * No need to run any init function, it dynamically resizes the data.
 */
namespace combinatorics {
    std::vector<mint> fact_, ifact_, inv_;

    void resize_data(int size) {
        if (fact_.empty()) {
            fact_ = {mint(1), mint(1)};
            ifact_ = {mint(1), mint(1)};
            inv_ = {mint(0), mint(1)};
        }
        for (int pos = fact_.size(); pos <= size; pos++) {
            fact_.push_back(fact_.back() * mint(pos));
            inv_.push_back(-inv_[MOD % pos] * mint(MOD / pos));
            ifact_.push_back(ifact_.back() * inv_[pos]);
        }
    }

    struct combinatorics_info {
        std::vector<mint> &data;

        combinatorics_info(std::vector<mint> &data) : data(data) {}

        mint operator[](int pos) {
            if (pos >= static_cast<int>(data.size())) {
                resize_data(pos);
            }
            return data[pos];
        }
    } fact(fact_), ifact(ifact_), inv(inv_);

    // From n choose k.
    // O(max(n)) in total.
    mint choose(int n, int k) {
        if (n < k || k < 0 || n < 0) {
            return mint(0);
        }
        return fact[n] * ifact[k] * ifact[n - k];
    }

    // From n choose k.
    // O(min(k, n - k)).
    mint choose_slow(int64_t n, int64_t k) {
        if (n < k || k < 0 || n < 0) {
            return mint(0);
        }
        k = std::min(k, n - k);
        mint result = 1;
        for (int i = k; i >= 1; i--) {
            result *= (n - i + 1);
            result *= inv[i];
        }
        return result;
    }

    // Number of balanced bracket sequences with n open and m closing brackets.
    mint catalan(int n, int m) {
        if (m > n || m < 0) {
            return mint(0);
        }
        return choose(n + m, m) - choose(n + m, m - 1);
    }

    // Number of balanced bracket sequences with n open and closing brackets.
    mint catalan(int n) {
        return catalan(n, n);
    }
} // namespace combinatorics

using namespace combinatorics;


namespace ext_combinatorics {
    // distribute n equal elements into k groups
    mint distribute(int n, int k) {
        return choose(n + k - 1, n);
    }

    // count number of seqs with n '(' and m ')' and bal always >= 0
    mint catalan_nm(int n, int m) {
        assert(n >= m);
        return choose(m + n, m) - choose(m + n, m - 1);
    }

    mint catalan(int n) {
        return catalan_nm(n, n);
    }

    // count number of bracket seqs, bal always >= 0
    mint catalan_bal(int n, int start_balance = 0, int end_balance = 0) {
        if ((n + start_balance + end_balance) % 2 != 0) return 0;
        if (start_balance < 0 || end_balance < 0) return 0;
        return choose(n, (n + end_balance - start_balance) / 2) - choose(n, (n - end_balance - start_balance - 2) / 2);
    }

    // from (0, 0) to (x, y)
    mint grid_path(int x, int y) {
        return choose(x + y, x);
    }

    // from (0, 0) to (x, y) not touch low y=x+b
    mint grid_path_low(int x, int y, int b) {
        if (b >= 0) return 0;
        return grid_path(x, y) - grid_path(y - b, x + b);
    }

    // from (0, 0) to (x, y) not touch up y=x+b
    // O((x + y) / |b2 - b1|)
    mint grid_path_up(int x, int y, int b) {
        if (b <= 0) return 0;
        return grid_path(x, y) - grid_path(y - b, x + b);
    }

    // from (0, 0) to (x, y) touch L -LU +LUL -LULU ....
    // O((x + y) / |b2 - b1|)
    mint grid_calc_LUL(int x, int y, int b1, int b2) {
        swap(x, y);
        x -= b1;
        y += b1;
        if (x < 0 || y < 0) return 0;
        return grid_path(x, y) - grid_calc_LUL(y, x, -b2, -b1);
    }

    // from (0, 0) to (x, y) not touch low y=x+b1, up y=x+b2
    // O((x + y) / |b2 - b1|)
    mint grid_path_2(int x, int y, int b1, int b2) {
        return grid_path(x, y) - grid_calc_LUL(x, y, b1, b2) - grid_calc_LUL(y, x, -b2, -b1);
    }

    // probability what we end in L+R after infinity random walk, if we start at L, and absorbing points is 0, L+R.
    mint gambler_ruin_right(int L, int R, mint p_right) {
        assert(L >= 1 && R >= 1);
        if (p_right * 2 == 1) return mint(L) / mint(L + R);
        if (p_right == 1) return 1;
        if (p_right == 0) return 0;
        mint v = (1 - p_right) / p_right;
        return (1 - v.power(L)) / (1 - v.power(L + R));
    }

    mint gambler_ruin_left(int L, int R, mint p_left) {
        return 1 - gambler_ruin_right(L, R, 1 - p_left);
    }
} // namespace ext_combinatorics



void solve() {
    int M, N; cin >> M >> N;
    map<pair<int, int>, mint> mem;
    function<mint(int, int)> calc_del = [&] (int m, int n) {
        assert(m >= 1);
        if (n == 0) return mint(1);
        if (m - 1 < n) return mint(0);
        if (n == 1) return mint(m - 1) * 2;
        if (mem.contains({m, n})) return mem[{m, n}];
        mint ans = choose(m - 1, n);
        for(int small = 2; small <= m; ++small) {
            ans += calc_del(m / small, n - 1);
        }
        return mem[{m, n}] = ans;
    };

    mint total = mint(M) * choose(M - 1, N - 1);
    for(int small = 1; small <= M; ++small) {
        total -= calc_del(M / small, N - 1);
    }
    cout << total << '\n';
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout << setprecision(12) << fixed;
    int t = 1;
//    cin >> t;
    rep(i, t) {
        solve();
    }
    return 0;
}

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

詳細信息

Test #1:

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

input:

4 3

output:

7

result:

ok 1 number(s): "7"

Test #2:

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

input:

11 4

output:

1187

result:

ok 1 number(s): "1187"

Test #3:

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

input:

100000 99999

output:

17356471

result:

ok 1 number(s): "17356471"

Test #4:

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

input:

11451 1919

output:

845616153

result:

ok 1 number(s): "845616153"

Test #5:

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

input:

99998 12345

output:

936396560

result:

ok 1 number(s): "936396560"

Test #6:

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

input:

100000 1

output:

0

result:

ok 1 number(s): "0"

Test #7:

score: 0
Accepted
time: 18ms
memory: 4492kb

input:

100000 15

output:

190067060

result:

ok 1 number(s): "190067060"

Test #8:

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

input:

10 3

output:

299

result:

ok 1 number(s): "299"

Test #9:

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

input:

10 4

output:

743

result:

ok 1 number(s): "743"

Test #10:

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

input:

10 5

output:

1129

result:

ok 1 number(s): "1129"

Test #11:

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

input:

15 6

output:

28006

result:

ok 1 number(s): "28006"

Test #12:

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

input:

15 7

output:

42035

result:

ok 1 number(s): "42035"

Test #13:

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

input:

123 45

output:

214851327

result:

ok 1 number(s): "214851327"

Test #14:

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

input:

998 244

output:

964050559

result:

ok 1 number(s): "964050559"

Test #15:

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

input:

1919 810

output:

379720338

result:

ok 1 number(s): "379720338"

Test #16:

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

input:

1048 576

output:

216543264

result:

ok 1 number(s): "216543264"

Test #17:

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

input:

999 777

output:

635548531

result:

ok 1 number(s): "635548531"

Test #18:

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

input:

99999 77777

output:

448144614

result:

ok 1 number(s): "448144614"

Test #19:

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

input:

34527 6545

output:

748108997

result:

ok 1 number(s): "748108997"

Test #20:

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

input:

12345 12

output:

777496209

result:

ok 1 number(s): "777496209"

Test #21:

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

input:

1 1

output:

0

result:

ok 1 number(s): "0"

Test #22:

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

input:

100000 10101

output:

855985819

result:

ok 1 number(s): "855985819"

Test #23:

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

input:

100000 91919

output:

92446940

result:

ok 1 number(s): "92446940"

Test #24:

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

input:

100000 77979

output:

106899398

result:

ok 1 number(s): "106899398"

Test #25:

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

input:

10000 11

output:

326411649

result:

ok 1 number(s): "326411649"

Test #26:

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

input:

100000 2

output:

15322970

result:

ok 1 number(s): "15322970"

Test #27:

score: 0
Accepted
time: 6ms
memory: 4436kb

input:

100000 3

output:

93355797

result:

ok 1 number(s): "93355797"

Test #28:

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

input:

100000 99998

output:

331850772

result:

ok 1 number(s): "331850772"

Test #29:

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

input:

100000 99996

output:

885066226

result:

ok 1 number(s): "885066226"

Test #30:

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

input:

13115 2964

output:

0

result:

ok 1 number(s): "0"

Test #31:

score: 0
Accepted
time: 17ms
memory: 4488kb

input:

100000 17

output:

425792977

result:

ok 1 number(s): "425792977"

Test #32:

score: 0
Accepted
time: 17ms
memory: 4380kb

input:

99991 16

output:

667323936

result:

ok 1 number(s): "667323936"

Test #33:

score: 0
Accepted
time: 13ms
memory: 4396kb

input:

99991 17

output:

627396741

result:

ok 1 number(s): "627396741"

Test #34:

score: 0
Accepted
time: 17ms
memory: 4496kb

input:

99991 18

output:

874158501

result:

ok 1 number(s): "874158501"

Test #35:

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

input:

100000 100000

output:

99999

result:

ok 1 number(s): "99999"

Test #36:

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

input:

94229 94229

output:

94228

result:

ok 1 number(s): "94228"

Test #37:

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

input:

94229 94223

output:

476599876

result:

ok 1 number(s): "476599876"

Test #38:

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

input:

2 1

output:

0

result:

ok 1 number(s): "0"

Test #39:

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

input:

2 2

output:

0

result:

ok 1 number(s): "0"

Test #40:

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

input:

3 1

output:

0

result:

ok 1 number(s): "0"

Test #41:

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

input:

3 2

output:

2

result:

ok 1 number(s): "2"

Test #42:

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

input:

3 3

output:

2

result:

ok 1 number(s): "2"

Test #43:

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

input:

9 2

output:

44

result:

ok 1 number(s): "44"

Test #44:

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

input:

9 3

output:

206

result:

ok 1 number(s): "206"

Test #45:

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

input:

9 4

output:

441

result:

ok 1 number(s): "441"

Test #46:

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

input:

9 7

output:

224

result:

ok 1 number(s): "224"

Test #47:

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

input:

70839 22229

output:

0

result:

ok 1 number(s): "0"

Test #48:

score: 0
Accepted
time: 11ms
memory: 4172kb

input:

65536 17

output:

698801006

result:

ok 1 number(s): "698801006"

Test #49:

score: 0
Accepted
time: 11ms
memory: 4184kb

input:

65535 17

output:

433312902

result:

ok 1 number(s): "433312902"

Test #50:

score: 0
Accepted
time: 6ms
memory: 4404kb

input:

99856 317

output:

932131332

result:

ok 1 number(s): "932131332"

Test #51:

score: 0
Accepted
time: 9ms
memory: 4432kb

input:

99856 318

output:

398997854

result:

ok 1 number(s): "398997854"

Test #52:

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

input:

99856 2

output:

984791559

result:

ok 1 number(s): "984791559"

Test #53:

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

input:

100000 50000

output:

309108799

result:

ok 1 number(s): "309108799"

Extra Test:

score: 0
Extra Test Passed