QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#779660 | #9553. The Hermit | fruian | WA | 24ms | 3800kb | C++14 | 2.2kb | 2024-11-24 20:53:38 | 2024-11-24 20:53:39 |
Judging History
answer
#include <bits/stdc++.h>
using i64 = long long;
using namespace std;
i64 p = 998244353;
i64 powmod(i64 a, i64 b) {
i64 res = 1;
while (b) {
if (b & 1) res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}
i64 C(i64 a, i64 b){
i64 res = 1;
for(int i = b; i>b-a;i--){
res *= i;
res %= p;
}
for(int i = 1;i<=a;i++){
res *= powmod(i, p-2);
res %= p;
}
return res;
}
void solve() {
int m, n;
cin>>m>>n;
i64 res = 0;
i64 hc = 1;
for(int i = m-n+1; i<=m-1;i++){
hc *= i;
hc %= p;
}
i64 k = 1;
for(int i = 1;i<=n-1;i++){
k *= i;
k %= p;
}
hc = hc*powmod(k, p-2)%p;
// cout<<hc<<endl;
for(int i = 1;i<=m-n+1;i++){
// cout<<m-i<<" "<<m-i-n+1<<" "<<hc<<endl;
res += hc;
hc = hc*(m-i-n+1)%p;
hc = hc*powmod(m-i, p-2)%p;
}
res *= n;
// cout<<res<<endl;
vector<int>dp(m+1, 2);
dp[1] = 1;
for(int i = 2;i<=m;i++){
for(int j = 2;;j++){
if(i*j>m)break;
dp[i*j] = max(dp[i]+1, dp[i*j]);
}
}
// for(int i = 1;i<=m;i++){
// cout<<dp[i]<<" ";
// }
for(int i = 1;i<=m-n+1;i++){
int bs = (m-i)/i;
int ok = 0;
// cout<<i<<" "<<dp[i]<<" "<<bs<<" "<<endl;
int ans = 0;
if(bs == 0)break;
for(int j = 1;j<=dp[i];j++){
int a = n-j;
if(a > bs)continue;
if(ans == 0){
ans = C(a, bs);
} else {
ans = ans * (a+1) % p;
ans = ans * powmod(bs-a, p-2) % p;
}
// cout<<a<<" "<<ans<<" "<<endl;
if(j==n-1){
ans *= 2;
res -= ans;
break;
}
res -= ans;
}
// cout<<res<<endl;
// cout<<endl;
}
// cout<<endl;
cout<<(res+p)%p<<endl;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t = 1;
// std::cin >> t;
while (t--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3548kb
input:
4 3
output:
7
result:
ok 1 number(s): "7"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
11 4
output:
1187
result:
ok 1 number(s): "1187"
Test #3:
score: 0
Accepted
time: 24ms
memory: 3800kb
input:
100000 99999
output:
17356471
result:
ok 1 number(s): "17356471"
Test #4:
score: -100
Wrong Answer
time: 5ms
memory: 3644kb
input:
11451 1919
output:
807161692
result:
wrong answer 1st numbers differ - expected: '845616153', found: '807161692'