自动搬运

查看原文

来自洛谷，原作者为

	COsm0s 知耻而后勇。

搬运于2025-08-24 23:03:11，当前版本为作者最后更新于2024-08-25 21:45:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

二项式反演。

题目里有“恰好”的标志，套路的，我们可以将它转化为至多/至少后再容斥回来。

当我们已经确定 $k$ 个 $2023$ 固定在这个数中时，我们发现，剩余的 $n-4k$ 个数就可以随便选——前提是不能有 $2023$。

也就是说，在剩余的数随便选时，我们可能会多选若干个 $2023$。

很容易想到这可以转化成“至少”的形式。

那么问题就转化成了两部分：

• 随便选剩余的数。

• 由“至少”推向“恰好”。

我们先来看第一部分。

当确定 $k$ 个 $2023$ 时，我们有 $k+1$ 个空可以插入那些随便选的数字。

举个例子：

x2023x2023x2023x

其中 x 代表的是一堆随便选的数字。

这是个经典的隔板法，讲这些数字分到 $k+1$ 个空的方案数为 ：

又因为题目明示了我们前导零的合法，所以再乘上每个数都有的 $0\sim 9$ 的 $10$ 种方案数，即为随便选的数的方案。

第二部分，直接套公式即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e6 + 5, N = 5e5 + 5, mod = 998244353;
int qpow(int b, int p) {
	int res = 1;
	while (p) {
		if (p & 1) {
			res = res * b % mod;
		}
		b = b * b % mod;
		p >>= 1;
	}
	return res;
}

int n, k, fac[maxn], ifac[maxn], g[N];

inline void init() {
	fac[0] = 1;
	for (int i = 1; i <= N; i ++) {
		fac[i] = fac[i - 1] * i % mod;
	}
	ifac[N] = qpow(fac[N], mod - 2);
	for (int i = N - 1; ~i; i --) {
		ifac[i] = ifac[i + 1] * (i + 1) % mod;
	}
}

inline int C(int n, int m) {
	if (n < m || n < 0 || m < 0) {
		return 0;
	} else {
		return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
	}
}
signed main() {
	cin >> n >> k, init();
	for(int m = k; m <= n / 4; m ++) {
		int p = n - 4 * m;
		g[m] = C(p + m, m) * qpow(10, p) % mod;
	}
	int ans = 0;
	for(int i = n / 4; i >= k; i --) {
		if(i - k & 1) ans = (ans - C(i, k) * g[i] % mod + mod) % mod;
		else ans = (ans + C(i, k) * g[i] % mod) % mod;
	}
	cout << ans << '\n';
	return 0;
}