QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#796123#9553. The Hermitlew2018WA 1303ms5940kbC++141.6kb2024-12-01 12:20:332024-12-01 12:20:33

Judging History

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

  • [2024-12-01 12:20:33]
  • 评测
  • 测评结果:WA
  • 用时:1303ms
  • 内存:5940kb
  • [2024-12-01 12:20:33]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define For(i, a, b) for (int i = (a); i <= (b); i++)
#define FOR(i, a, b) for (int i = (a); i >= (b); i--)
#define int long long

const int N = 1e5 + 5;
const int mod = 998244353;
int n, m, cnt[N];
ll fac[N], inv[N], ans;

int qpow(int a, int b) {
	int res = 1;
	while (b) {
		if (b & 1) res = (ll)res * a % mod;
		a = (ll)a * a % mod;
		b >>= 1;
	}
	return res;
}

// m个数里选n个
ll c(int m, int n) {
	if (n == m) return 1;
	if (n > m || n < 0) return 0;
	return (fac[m] * inv[n] % mod * inv[m - n] % mod) % mod;
}

void dfs(int u, int len) {
	//cout << "u = " << u << " len = " << len << endl;
	if (len == n) {
		ans -= 1;
		return;
	}
	(ans -= c(cnt[u] - 1, n - len)) %= mod;
	for (int j = 2 * u; j <= m; j += u) {
		dfs(j, len + 1);
	}
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> m >> n;
	if (n == 1) {
		cout << "0" << endl;
		return 0;
	}
	fac[0] = 1;
	For (i, 1, m) {
		fac[i] = (ll)fac[i - 1] * i % mod;
		inv[i] = qpow(fac[i], mod - 2); 
	}
	For (i, 1, n) {
		int tot = 0;
		for (int j = i; j <= m; j += i) tot++;
		cnt[i] = tot;
	}
	ans = c(m, n) * n % mod;
	// 枚举删的第一个数
	for (int i = 1; i <= m; i++) {
		(ans -= c(cnt[i] - 1, n - 1)) %= mod;
		// 枚举删的第二个数
		for (int j = 2 * i; j <= m; j += i) {
			dfs(j, 2);
		}
	}
	cout << (ans + mod) % mod << endl;
	return 0;
}   

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3696kb

input:

4 3

output:

7

result:

ok 1 number(s): "7"

Test #2:

score: 0
Accepted
time: 1ms
memory: 5720kb

input:

11 4

output:

1187

result:

ok 1 number(s): "1187"

Test #3:

score: 0
Accepted
time: 1303ms
memory: 5940kb

input:

100000 99999

output:

17356471

result:

ok 1 number(s): "17356471"

Test #4:

score: 0
Accepted
time: 32ms
memory: 3936kb

input:

11451 1919

output:

845616153

result:

ok 1 number(s): "845616153"

Test #5:

score: 0
Accepted
time: 1303ms
memory: 5264kb

input:

99998 12345

output:

936396560

result:

ok 1 number(s): "936396560"

Test #6:

score: 0
Accepted
time: 0ms
memory: 3680kb

input:

100000 1

output:

0

result:

ok 1 number(s): "0"

Test #7:

score: -100
Wrong Answer
time: 1302ms
memory: 5172kb

input:

100000 15

output:

580649349

result:

wrong answer 1st numbers differ - expected: '190067060', found: '580649349'