QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#775498 | #9553. The Hermit | guiyuan98# | WA | 458ms | 42084kb | C++20 | 3.1kb | 2024-11-23 16:05:16 | 2024-11-23 16:05:16 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define linf 1e18
#define pb push_back
#define siz size()
#define int long long
#define ll long long
#define ld long double
#define PII pair<int, int>
const int mod = 998244353;
using i64 = long long;
using u64 = unsigned long long;
const int N = 1e5 + 10;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
namespace my128
{
using i128 = __int128_t;
i128 abs(const i128 &x) { return x > 0 ? x : -x; }
auto &operator>>(istream &it, i128 &j)
{
string val;
it >> val;
i128 ans = 0;
bool f = 0; // 负数标记
for (char c : val)
{
if (c == '-')
f = 1;
else if (c >= '0' && c <= '9')
ans = ans * 10 + c - '0';
}
j = f ? -ans : ans;
return it;
}
auto &operator<<(ostream &os, const i128 &j)
{
string ans;
function<void(i128)> write = [&](i128 x)
{ if (x < 0) ans += '-', x = -x; if (x > 9) write(x / 10); ans += x % 10 + '0'; };
write(j);
return os << ans;
}
}
using namespace my128;
// my128::i128 a, b;
int qpow(int a, int b)
{
int res = 1;
while (b)
{
if (b & 1)
res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
struct myhash
{
static uint64_t hash(uint64_t x)
{
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const
{
static const uint64_t SEED =
chrono::steady_clock::now().time_since_epoch().count();
return hash(x + SEED);
}
size_t operator()(pair<uint64_t, uint64_t> x) const
{
static const uint64_t SEED =
chrono::steady_clock::now().time_since_epoch().count();
return hash(x.first + SEED) ^ (hash(x.second + SEED) >> 1);
}
};
ll fac[N], invfac[N];
void init(int n)
{
fac[0] = 1;
for (int i = 1; i <= n; i++)
fac[i] = fac[i - 1] * i % mod;
invfac[n] = qpow(fac[n], mod - 2);
for (int i = n - 1; i >= 0; i--)
invfac[i] = invfac[i + 1] * (i + 1) % mod;
}
i64 C(int n, int m)
{ // 组合数
if (m > n || m < 0)
return 0;
return fac[n] * invfac[m] % mod * invfac[n - m] % mod;
}
i64 A(int n, int m)
{ // 排列数
if (m > n || m < 0)
return 0;
return fac[n] * invfac[n - m] % mod;
}
i64 catalan(int n)
{ // 卡特兰数
if (n < 0)
return 0;
return C(2 * n, n) * qpow(n + 1, mod - 2) % mod;
}
void solve()
{
int n, m;
cin >> m >> n;
unordered_map<int, unordered_map<int, int, myhash>, myhash> f;
init(m);
for (int i = 1; i <= m; i++)
f[1][i] = 1;
for (int i = 2; i <= n; i++)
for (auto [x, y] : f[i - 1])
for (int j = 2; j * x <= m; j++)
f[i][j * x] = (f[i][j * x] + f[i - 1][x]) % mod;
int ans = n * C(m, n) % mod;
for (int i = 1; i <= n; i++)
for (auto [x, y] : f[i])
ans = ans - y * C(m / x - 1, n - i) % mod + mod % mod;
cout << ans;
}
signed main()
{
IOS;
int t = 1;
// cin >> t;
while (t--)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3616kb
input:
4 3
output:
7
result:
ok 1 number(s): "7"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
11 4
output:
1187
result:
ok 1 number(s): "1187"
Test #3:
score: 0
Accepted
time: 458ms
memory: 42084kb
input:
100000 99999
output:
17356471
result:
ok 1 number(s): "17356471"
Test #4:
score: -100
Wrong Answer
time: 24ms
memory: 6708kb
input:
11451 1919
output:
-3147361259
result:
wrong answer 1st numbers differ - expected: '845616153', found: '-3147361259'