本文主要是介绍ARC144，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

A

容易发现最优的构造方案一定有 \(2m=n\)，且 \(x\) 每一位不超过 \(4\)。

于是 \(x\) 第一位填 \(n\bmod 4\)（如果 \(4\vert n\) 那就填 \(4\)），后面全填 \(4\) 即可。

B

二分。由于 \(a\le b\)，可以证明一定不会在一个数上又加又减。所以 \(O(n)\) check 即可。

C

算是思维题，但思路是非常自然的。

首先，当 \(2k>n\) 时无解。否则前 \(k\) 个数一定是 \(k+1,k+2...2k\)。

考虑 \(1\sim k\) 这些数。我们希望马上就把它们接在后面。为保证有解，最多能在后面接到 \(1\sim \min(k,n-3k)\)。

原因是如果超过了 \(n-3k\) 那么后面是一个剩下不到 \(2k\) 个空的子问题，无解。

然后再后面的可以当作一个子问题递归处理。但注意数集不再是 \(1\sim n\)，拿个数组存一下就好了。

这里有个结论没证，就是为什么后面的那些空明明数集都不同却能当作和原问题相同的子问题？

其实我证不来，VP的时候感性理解觉得是对的就直接莽上去了。

#include <cstdio>

inline int min(const int x, const int y) {return x < y ? x : y;}
int a[300005];
void solve(int n, int k, int st) {
	if (n <= 3 * k) {
		for (int i = k + 1; i <= n; ++ i) printf("%d ", a[i + st]);
		for (int i = 1; i <= k; ++ i) printf("%d ", a[i + st]);
		return;
	}
	for (int i = k + 1; i <= 2 * k; ++ i) printf("%d ", a[i + st]);
	int t = min(k, n - 3 * k);
	for (int i = 1; i <= t; ++ i) printf("%d ", a[i + st]);
	for (int i = 2 * k; i >= k + t + 1; -- i) a[i + st] = a[i - k + st];
	solve(n - k - t, k, st + k + t);
}

int main() {
	int n, k;
	scanf("%d%d", &n, &k);
	if (n - k < k) return puts("-1"), 0;
	for (int i = 1; i <= n; ++ i) a[i] = i;
	solve(n, k, 0);
	return 0;
}

D

题目中对 \(f\) 的限制十分的强，以至于可以直接推导出：对于任意 \(x\)，\(f(x)\) 等于它每一位的 \(f\) 值总和减去 \((\operatorname{popcount}(x)-1)\cdot f(0)\)。

那么我们就只需要关心 \(f(0),f(2^0),f^(2^1)...2(2^{n-1})\) 的值了。目标是使得 \(0\le \min\left\{f(i)\right\},\max\left\{f(i)\right\}\le k\)。

容易想到令每个 \(f(i)\) 都减去 \(f(0)\)。记原本的 \(f(0)\) 为 \(x\)，所有为正数的 \(f\) 之和为 \(S^+\)，所有为负数的 \(f\) 之和为 \(S^-\)。这样的话要求变为 \(0\le S^-+x,f(0)+S^++x\le k\)，即 \(-S^-\le x\le k-S^+\)。

那么我们要数的就是 \(\sum k-S^++S^-+1\) 的和（连这一步转化都没想到，菜）。

然后还有一个更加牛逼的转化：把 \(-S^++S^-\) 转化为 \(-\sum \vert f(i)\vert\)。

转化过后我们发现这玩意儿貌似可以组合数算了？

直接求 \(k-\sum\vert f(i)\vert+1\) 的和肯定不能组合数。可以搞点废话文学式子，把 \(k-\sum\vert f(i)\vert+1\) 变形成 \(\sum\limits_{i=0}^k[\vert f\vert\le i]\)。

考虑最终答案的构成：先确定有多少个 \(f\) 非 \(0\)，然后确定符号，再对 \(\sum\limits_{i=0}^k[\vert f\vert\le i]\) 求和。

答案就是

\[\sum\limits_{i=0}^n2^i\tbinom{n}{i}\sum\limits_{j=0}^k\tbinom{j}{i} \]

\(\tbinom{j}{i}\) 是插板出来的。

由基本组合恒等式得到上式等于

\[\sum\limits_{i=0}^n2^i\tbinom{n}{i}\tbinom{k+1}{i+1} \]

可以直接 \(O(n)\) 计算。

#include <cstdio>

const int mod = 998244353;
inline int qpow(int a, int b) {
	int ret = 1;
	while (b) {
		if (b & 1) ret = 1ll * ret * a % mod;
		a = 1ll * a * a % mod, b >>= 1;
	}
	return ret;
}
int fact[300005], inv[300005];
inline int C(int n, int m) {
	return 1ll * fact[n] * inv[m] % mod * inv[n - m] % mod;
}

int main() {
	int n, ans = 0;
	long long k;
	scanf("%d%lld", &n, &k);
	k %= mod;
	fact[0] = 1;
	for (int i = 1; i <= n + 1; ++ i) fact[i] = 1ll * fact[i - 1] * i % mod;
	inv[n + 1] = qpow(fact[n + 1], mod - 2);
	for (int i = n; i >= 0; -- i) inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;
	for (int i = 0, j = 1, x = k + 1; i <= n && i <= k; x = 1ll * x * (k - i ? k - i : 1) % mod, ++ i, j = (j << 1) % mod)
		ans = (ans + 1ll * j * C(n, i) % mod * x % mod * inv[i + 1]) % mod;
	printf("%d", ans);
	return 0;
}

这篇关于ARC144的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！