QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#776410 | #9553. The Hermit | Guren_ | WA | 13ms | 9804kb | C++14 | 1.7kb | 2024-11-23 18:31:29 | 2024-11-23 18:31:30 |
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;
}
cout << (ans - cnt + mod) % mod << endl;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 13ms
memory: 9804kb
input:
4 3
output:
7 8
result:
wrong answer Output contains longer sequence [length = 2], but answer contains 1 elements