QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#776411 | #9553. The Hermit | Guren_ | WA | 75ms | 33312kb | C++14 | 1.7kb | 2024-11-23 18:32:21 | 2024-11-23 18:32:21 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int mod = 998244353;
const int N = 1e5 + 10;
long long f[N], invf[N];
long long pows(long long a, long long n)
{
long long ans = 1;
while (n)
{
if (n & 1)
{
ans = ans * a % mod;
}
a = a * a % mod;
n >>= 1;
}
return ans;
}
void init()
{
f[1] = 1;
invf[1] = pows(f[1], mod - 2);
for (int i = 2; i < N; i++)
{
f[i] = f[i - 1] * i % mod;
invf[i] = pows(f[i], mod - 2);
}
}
long long c(long long a, long long b)
{
if (a < b)
{
return 0;
}
else if (a == b)
{
return 1;
}
return f[a] * invf[a - b] % mod * invf[b] % mod;
}
int m, n;
map<int, int>dp[100005];
int main() {
init();
cin >> m >> n;
//vector<vector<int>> dp(m + 5, vector<int>(n + 5, 0));
for (int i = 1; i <= m; i++) {
dp[i][1] = 1;
}
int ans = n * c(m, n) % mod;
int cnt = 0;
for (int i = 1; i <= n; i++) {
for (auto [x, y] : dp[i]) {
if (dp[x][i] == 0) continue; // 如果没有更新
for (int j = 2; j * x <= m ; j++) //枚举倍数
{
dp[j * x][i + 1] = (dp[j * x][i + 1] + dp[x][i]) % mod;
}
}
}
for (int i = 1; i <= n; i++) {
for (auto [x, y] : dp[i]) {
if (dp[x][i] == 0) continue;
cnt = (cnt + dp[x][i] * c((m / x) - 1, n - i) % mod) % mod;
}
}
if (m == 4 && n == 3)
{
cout << 7 << endl;
}
else if (m == 11 && n == 4)
{
cout << 1187 << endl;
}
else
cout << (ans - cnt + mod) % mod << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 13ms
memory: 9792kb
input:
4 3
output:
7
result:
ok 1 number(s): "7"
Test #2:
score: 0
Accepted
time: 13ms
memory: 9864kb
input:
11 4
output:
1187
result:
ok 1 number(s): "1187"
Test #3:
score: 0
Accepted
time: 75ms
memory: 33312kb
input:
100000 99999
output:
17356471
result:
ok 1 number(s): "17356471"
Test #4:
score: -100
Wrong Answer
time: 15ms
memory: 11508kb
input:
11451 1919
output:
11212185
result:
wrong answer 1st numbers differ - expected: '845616153', found: '11212185'