QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#766578 | #9553. The Hermit | IntStar# | WA | 188ms | 34556kb | C++17 | 1.6kb | 2024-11-20 17:49:38 | 2024-11-20 17:49:45 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std ;
const int N = 3e5 + 10 , mod = 998244353 ;
typedef pair<int , int> PII ;
mt19937_64 rng(random_device{}());
int n , m , k ;
int w[N] ;
int f[N][30] ;
int fact[N] , infact[N] , p[N] ;
int qmi(int a, int k, int p){
int res = 1;
while (k){
if (k & 1) res = res * a % p;
a = a * a % p;
k >>= 1;
}
return res ;
}
int C(int a , int b){ // a 中 取 b 个
return fact[a] * infact[b] % mod * infact[a - b] % mod ;
}
vector<int> get(int x){
vector<int> res ;
for(int i = 1 ; i <= x / i ; i ++){
if(i == x)continue ;
if(x % i == 0){
res.push_back(i) ;
if(x / i != i and x / i != x){
res.push_back(x / i) ;
}
}
}
return res ;
}
void solve(){
cin >> n >> m ;
int res = C(n , m) * m % mod ;
for(int i = 1 ; i <= n ; i ++){
auto vc = get(i) ;
f[i][1] = 1 ;
for(int j = 2 ; j <= 18 ; j ++){
for(auto c : vc){
f[i][j] = (f[i][j] + f[c][j - 1]) % mod ;
}
}
int cnt = n / i - 1 ;
for(int j = 1 ; j <= 18 ; j ++){
int d = m - j ;
if(d < 0 or d > cnt)continue ;
res = (res - f[i][j] * C(cnt , d) % mod) ;
}
}
cout << (res + mod) % mod ;
}
signed main(){
ios::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0) ;
int t = 1 ;
fact[0] = infact[0] = 1;
for (int i = 1; i < N / 2 ; i ++)
{
fact[i] = fact[i - 1] * i % mod;
infact[i] = infact[i - 1] * qmi(i, mod - 2, mod) % mod;
}
// cin >> t ;
while(t --){
solve() ;
}
return 0 ;
}
/* /\_/\
* (= ._.)
* / > \>
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 15ms
memory: 11768kb
input:
4 3
output:
7
result:
ok 1 number(s): "7"
Test #2:
score: 0
Accepted
time: 18ms
memory: 9712kb
input:
11 4
output:
1187
result:
ok 1 number(s): "1187"
Test #3:
score: 0
Accepted
time: 188ms
memory: 34556kb
input:
100000 99999
output:
17356471
result:
ok 1 number(s): "17356471"
Test #4:
score: -100
Wrong Answer
time: 28ms
memory: 13864kb
input:
11451 1919
output:
-152628200
result:
wrong answer 1st numbers differ - expected: '845616153', found: '-152628200'