调试了好几次都是90分,第五个测试点WA
查看原帖
调试了好几次都是90分,第五个测试点WA
815093
AAAAAZBX楼主2023/5/25 23:54
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
int n, m;
int sum[2020];
int st[2020];
int primes[2020];
int cnt;
void get_primes(int n)
{
	for (int i = 2; i <= n; i++)
	{
		if (!st[i])primes[cnt++] = i;
		for (int j = 0; primes[j] <= n / i; j++)
		{
			st[primes[j] * i] = 1;
			if (i % primes[j] == 0)break;
		}
	}
}
int get(int n, int p)
{
	int res = 0;
	while (n)
	{
		res += n / p;
		n /= p;
	}
	return res;
}
vector<int> mul(vector<int> a, int b)
{
	int t = 0;
	vector<int> c;
	for (int i = 0; i < a.size(); i++)
	{
		t += a[i] * b;
		c.push_back(t % 10);
		t /= 10;
	}
	while (t)
	{
		c.push_back(t%10);
		t /= 10;
	}
	return c;
}
vector<int> sub(vector<int> A, vector<int> B)
{
	vector<int> C;
	for (int i = 0, t = 0; i < A.size(); i++)
	{
		t = A[i] - t;
		if (i < B.size()) t -= B[i];
		C.push_back((t + 10) % 10);
		if (t < 0) t = 1;
		else t = 0;
	}
	while (C.size() > 1 && C.back() == 0) C.pop_back();
	return C;
}

int main()
{
	scanf("%d%d", &n, &m);
	vector<int> res;
	res.push_back(1);
	res = mul(res, n + 2);
	get_primes(n + 3);
	for (int i = 0; i < cnt; i++)
		sum[i] = get(n + 3, primes[i]) - get(n + 3 - m, primes[i]) - get(m, primes[i]);
	for (int i = 0; i < cnt; i++)
		for (int j = 0; j < sum[i]; j++)
			res = mul(res, primes[i]);
	vector<int> ans;
	ans.push_back(1);
	for (int i = 0; i < cnt; i++)
		sum[i] = get(n + 2, primes[i]) - get(n + 2 - m, primes[i]) - get(m, primes[i]);
	for (int i = 0; i < cnt; i++)
		for (int j = 0; j < sum[i]; j++)
			ans = mul(ans, primes[i]);
	ans = mul(ans, 2);
	vector<int> C = sub(res, ans);
	for (int i = 1; i <= m; i++)
		C = mul(C, i);
	for (int i = 1; i <= n + 1; i++)
		C = mul(C, i);
	for (int i = C.size() - 1; i >= 0; i--)
		printf("%d", C[i]);
	return 0;
}
2023/5/25 23:54
加载中...