QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#829205 | #9553. The Hermit | ucup-team4435# | AC ✓ | 18ms | 4564kb | C++23 | 11.5kb | 2024-12-24 06:57:09 | 2024-12-24 06:57:14 |
Judging History
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,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
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