AtCoder Grand Contest 036 – 解题报告

A – Triangle

三角形斜着放即可。

// A.cpp
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll S;

int main()
{
	scanf("%lld", &S);
	ll y = (S + int(1e9) - 1) / int(1e9), x = y * int(1e9) - S;
	printf("%d %d %d %d %lld %lld\n", 0, 0, int(1e9), 1, x, y);
	return 0;
}

B – Do Not Duplicate

看到 \(k \leq 10^{18}\) 之后肯定觉得跟倍增或者是矩阵快速幂有关。

记 \(ans_i\) 为向空串添加 \(a_i, a_{i + 1}, a_{i + 2}, \dots\) 的结果，特别地，设 \(ans_0\) 为空串。刚开始的时候串是 \(ans_1\)，当第二次迭代到 \(a_j\) 遇到 \(ans_1[0]\)，也就是头元素之后，整个串会被清空，则最后答案会变成 \(ans_{j + 1}\)。疯狂迭代的过程用倍增即可。

// B.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2e5 + 200, LOG = 60;

int n, ai[MAX_N], mem[MAX_N], nxt[MAX_N], up[LOG][MAX_N], ansBox[MAX_N];
long long k;

int main()
{
	scanf("%d%lld", &n, &k);
	for (int i = 1; i <= n; i++)
		scanf("%d", &ai[i]);
	for (int i = n; i >= 1; i--)
		mem[ai[i]] = i;
	for (int i = n; i >= 1; i--)
		nxt[i] = mem[ai[i]], mem[ai[i]] = i;
	up[0][0] = 1;
	for (int i = n; i >= 1; i--)
		if (nxt[i] <= i)
			if (nxt[i] == n)
				up[0][i] = 0;
			else
				up[0][i] = nxt[i] + 1;
		else if (nxt[i] == n)
			up[0][i] = 1;
		else
			up[0][i] = up[0][nxt[i] + 1];
	for (int i = 1; i < LOG; i++)
		for (int j = 0; j <= n; j++)
			up[i][j] = up[i - 1][up[i - 1][j]];
	int ans = 0;
	for (int i = LOG - 1; i >= 0; i--)
		if (k & (1LL << i))
			ans = up[i][ans];
	memset(mem, 0, sizeof(mem));
	int tot = 0;
	if (ans == 0)
		return 0;
	for (int i = ans; i <= n; i++)
	{
		if (mem[ai[i]] == 0)
			ansBox[++tot] = ai[i], mem[ai[i]] = tot;
		else
		{
			int pos = mem[ai[i]];
			while (tot >= pos)
				mem[ansBox[tot--]] = 0;
		}
	}
	for (int i = 1; i <= tot; i++)
		printf("%d ", ansBox[i]);
	puts("");
	return 0;
}

C – GP 2

这个题很有意思的，性质叠加题。

首先，一共有 \(m\) 次机会对 \(a_i\) 进行奇偶转换，所以奇数最多只有 \(m\) 个，且一个数最大不超过 \(2m\)。所以，最后答案要求的是这样的数列，满足：

• \(\sum a_i = 3m\)
• \(\sum_{i = 1}^n [a_i \bmod 2 \equiv 1] \leq m\)
• \(\sum_{i = 1}^n [a_i \leq 2m] = 0\)

我们先把第三个条件抛开，只算满足前两个性质的数列。显然，这样的数列的个数是：

\[ \sum_{i = 1}^m [i \bmod 2 \equiv 3m \bmod 2] {\frac{3m – i}{2} + n – 1 \choose n – 1} {n \choose i} \]

这个很容易理解。如何满足第三个条件呢？我们可以考虑固定一个元素至少为 \(2m + 1\)，然后把 \(3m\) 变成 \(m – 1\) 去计数即可。当然，被容斥掉的部分要乘个 \(n\)。

// C.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 3e6 + 200, mod = 998244353;

int fac[MAX_N], fac_inv[MAX_N], inv[MAX_N];

void preprocess()
{
	for (int i = fac[0] = 1; i < MAX_N; i++)
		fac[i] = 1LL * fac[i - 1] * i % mod;
	inv[0] = inv[1] = fac_inv[0] = 1;
	for (int i = 2; i < MAX_N; i++)
		inv[i] = 1LL * (mod - mod / i) * inv[mod % i] % mod;
	for (int i = 1; i < MAX_N; i++)
		fac_inv[i] = 1LL * fac_inv[i - 1] * inv[i] % mod;
}

int binomial(int n_, int k_) { return (n_ < k_) ? 0 : 1LL * fac[n_] * fac_inv[k_] % mod * fac_inv[n_ - k_] % mod; }

int calc(int n, int m, int o)
{
	int ret = 0;
	for (int i = 0; i <= o; i++)
		if (i % 2 == m % 2)
			ret = (0LL + ret + 1LL * binomial((m - i) / 2 + n - 1, n - 1) * binomial(n, i) % mod) % mod;
	return ret;
}

int main()
{
	int n, m;
	preprocess(), scanf("%d%d", &n, &m);
	printf("%lld\n", (0LL + calc(n, 3 * m, m) + mod - 1LL * n * calc(n, m - 1, m) % mod) % mod);
	return 0;
}