QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#755745 | #9553. The Hermit | ucup-team059# | WA | 2ms | 9412kb | C++20 | 3.7kb | 2024-11-16 17:58:58 | 2024-11-16 17:58:59 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
#define PII pair<int,int>
#define PIII pair<int,PII>
#define endl '\n'
#define int long long
//#define int __int128
#define i64 long long
#define lc p<<1
#define rc p<<1|1
using namespace std;
const int N = 1e5 + 10, mod = 998244353;
//bool isprime[N];
//int prime[N];
//int cnt;
//void euler(int n) {
// memset(isprime, true, sizeof(isprime));
// isprime[1] = false;
// for (int i = 2; i <= n; ++i) {
// if (isprime[i]) prime[++cnt] = i;
// for (int j = 1; j <= cnt && i * prime[j] <= n; ++j) {
// isprime[i * prime[j]] = false;
// if (i % prime[j] == 0) break;
// }
// }
//}
int pre[N];
int rk[N];
void init(int n) {
for (int i = 1; i <= n; i++) {
pre[i] = i;
rk[i] = 1;
}
}
int find(int x) {
if (pre[x] == x) return x;
return pre[x] = find(pre[x]);
}
bool isSame(int x, int y) {
return find(x) == find(y);
}
int ans[N];
bool join(int x, int y) {
x = find(x);
y = find(y);
ans[x] = ans[y] = max(ans[x], ans[y]);
if (x == y) return false;
if (rk[x] > rk[y]) pre[y] = x;
else {
if (rk[x] == rk[y]) rk[y]++;
pre[x] = y;
}
return true;
}
int qpow(int x, int n) {
int ans = 1;
while (n) {
if (n & 1) {
ans *= x;
ans %= mod;
}
x *= x;
x %= mod;
n >>= 1;
}
return ans;
}
int fac[N], inv[N];
void fact(int n) {
fac[0] = 1;
for (int i = 1; i <= n; i++) {
fac[i] = fac[i - 1] * i % mod;
}
inv[n] = qpow(fac[n], mod - 2);
for (int i = n - 1; i >= 0; i--) {
inv[i] = inv[i + 1] * (i + 1) % mod;
}
}
int C(int n, int m) {
if (m > n)return 0;
return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
bool st[N];
int prime[N];
int cnt;
int mu[N];
int smu[N];
int a[N];
int cnt1[N];
void init() {
mu[1] = 1;
for (int i = 2; i < N; i++) {
if (!st[i]) {
mu[i] = -1;
prime[++cnt] = i;
}
for (int j = 1; j <= cnt && i * prime[j] < N; j++) {
st[i * prime[j]] = true;
if (i % prime[j] == 0) break;
mu[i * prime[j]] = -mu[i];
}
}
for(int i=1;i<N;i++){
smu[i]=smu[i-1]+mu[i];
}
}
int f[N][30];
int sss[N];
void solve() {
int n, m, k;
cin >> m >> n;
fact(m);
init();
int s1=0,s11=0,s0=0;
int res = 0;
for (int i = 1; i <=m; i++) {
for (int j = 1; j * j <= i; j++) {
if (i % j == 0) {
if(j!=1)res = (res - mu[j] * (qpow(2, cnt1[j]))) % mod;
res = (res % mod + mod) % mod;
cnt1[j]++;
if (j * j != i){
if(i/j!=1)res = (res - mu[i / j] * (qpow(2, cnt1[i / j]))) % mod;
res = (res % mod + mod) % mod;
cnt1[i / j]++;
}
}
}
sss[i]=res;
// cout<<res<<endl;
}
int ans = 0;
for (int i = 1; i <= m; i++) {
f[i][0] = 1;
f[i][1] = 1;
}
f[1][1] = 1;
for (int i = 2; i <= m; i++) {
for (int j = 1; j * j <= i; j++) {
if (i % j == 0) {
for (int l = 0; l <= 20; l++) {
f[i][l + 1] += f[j][l];
}
}
}
}
for (int i = 1; i <= m / 3; i++) {
int x = (m - i) / i;
int y = m - i - x;
int sum = 0;
for (int j = 0; j <= 20 && n > j + 1; j++) {
int s = C(m / i - 1, n - j);
// cout << m / i - 1 << ' ' << n - j << endl;
// cout << s;
int del=0;
for (int l = 2; m / i / l >= n - j; l++) {
s += C(m / i / l, n - j)*mu[m / i / l] % mod % mod;
del+=C(m / i / l, n - j)*mu[m / i / l] % mod;
cout << '-' << C(m / i / l, n - j)*mu[m / i / l] % mod;
s %= mod;
}
// cout<<"del:"<<del<<endl;
sum += s * f[i][j];
ans += (s + mod) % mod * (n - j) * f[i][j] % mod;
ans %= mod;
// cout << sum << endl;
}
// cout << sum << ' ';
// cout << ans << endl;
}
cout << ans << endl;
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
ll t = 1;
// cin >> t;
while (t--) {
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 9412kb
input:
4 3
output:
--17
result:
wrong output format Expected integer, but "--17" found