QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#755745#9553. The Hermitucup-team059#WA 2ms9412kbC++203.7kb2024-11-16 17:58:582024-11-16 17:58:59

Judging History

你现在查看的是最新测评结果

  • [2024-11-18 19:43:48]
  • hack成功,自动添加数据
  • (/hack/1196)
  • [2024-11-16 17:58:59]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:9412kb
  • [2024-11-16 17:58:58]
  • 提交

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