2026 杭电暑期多校 8-1003-太近就不合法了

题目大意

太近就不合法了

时间限制：3000 MS (Others) / 6000 MS (Java)

内存限制：524288 KB (Others) / 524288 KB (Java)

有 $n$ 个依次排列的位置，编号为 $1, 2, \ldots, n$。

每次询问给出两个整数 $x, k$。你需要选择若干位置，满足以下两个条件：

1. 位置 $x$ 不能被选择。

2. 任意两个被选择的位置的编号之差的绝对值不小于 $k$。

每次询问相互独立。请你求出每次询问的合法选择方案数。注意，允许不选择任何位置。由于答案可能很大，请将结果对 $998244353$ 取模后输出。

第一行包含一个整数 $T$，表示测试数据的组数。

对于每组测试数据：

第一行包含两个整数 $n, q$，分别表示位置的数量和询问的数量。

接下来 $q$ 行，每行包含两个整数 $x_i, k_i$，表示一次询问。

数据范围与约定：

• $T = 10^4$

• $1 \le n, q \le 10^5$

• $1 \le x_i, k_i \le n$

• $\sum n = 10^6$

• $\sum q = 10^6$

对于每次询问，输出一行一个整数，表示合法的选择方案数对 $998244353$ 取模后的结果。

Plaintext

3
5 2
3 2
4 3
1 2
1 1
1 1
3 2
2 1
1 3

Plaintext

9
7
1
1
4
3

第一组测试数据：

• 共有 $5$ 个位置，即 $\{1, 2, 3, 4, 5\}$。

• 第一次询问（$x=3, k=2$）：不能选择位置 $3$，且相邻选择的位置距离至少为 $2$。合法的方案有 $9$ 种，分别为：空集 $\emptyset$, $\{1\}$, $\{2\}$, $\{4\}$, $\{5\}$, $\{1, 4\}$, $\{1, 5\}$, $\{2, 4\}$, $\{2, 5\}$。

• 第二次询问（$x=4, k=3$）：不能选择位置 $4$，且相邻选择的位置距离至少为 $3$。合法的方案有 $7$ 种，分别为：空集 $\emptyset$, $\{1\}$, $\{2\}$, $\{3\}$, $\{5\}$, $\{1, 5\}$, $\{2, 5\}$（注意 $\{1, 4\}$ 不合法因为包含了 $4$）。

第二组测试数据：

• 只有 $1$ 个位置，即 $\{1\}$。

• 两次询问均为 $x=1, k=1$，不能选择位置 $1$。唯一合法的方案是不选择任何位置，即空集 $\emptyset$，方案数为 $1$。

第三组测试数据：

• 共有 $3$ 个位置，即 $\{1, 2, 3\}$。

• 第一次询问（$x=2, k=1$）：不能选择位置 $2$，相邻位置距离至少为 $1$。合法方案有 $4$ 种：$\emptyset$, $\{1\}$, $\{3\}$, $\{1, 3\}$。

• 第二次询问（$x=1, k=3$）：不能选择位置 $1$，相邻位置距离至少为 $3$。合法方案有 $3$ 种：$\emptyset$, $\{2\}$, $\{3\}$。

思路讲解

下面的这个组合式子，可以比较简单的使用这个映射来证明啊。

$$f(m, k) = \sum_{c=0}^{\lfloor \frac{m+k-1}{k} \rfloor} \binom{m - (c-1)(k-1)}{c}$$

constexpr ll SQRT = 200;

ll f_cal(ll m, ll k) {
	ll ans = 0;
	ll up = (m + k - 1) / k;
	for (int c = 0; c <= up; ++c) {
		ans += CC(m - (c - 1) * (k - 1), c);
		ans %= mod;
	}
	ans %= mod;
	if (ans < 0) ans += mod;
	return ans;
}

void Solve() {
	Cin(N, Q);
	map<ll, vector<ll> > mp;
	vector<vector<ll> > F(N + 2, vector<ll>(min(N, SQRT) + 2));
	
	for (int k = 1; k <= min(N, SQRT); ++k) {
		F[0][k] = 1;
		for (int i = 1; i <= N; ++i) {
			F[i][k] = F[i - 1][k] + (i - k < 0 ? 1 : F[i - k][k]);
			F[i][k] %= mod;
		}
	}
	for (int _ = 1; _ <= Q; ++_) {
		ll x, k;
		Cin(x, k);
		ll up = (N + k - 1) / k;
		if (k > SQRT) {
			// 这个的计算是 k 越小，计算的越多的啊。
			ll ans = f_cal(N, k) - (x - k < 0 ? 1 : f_cal(x - k, k)) * (
				         N - x - k + 1 < 0 ? 1 : f_cal(N - x - k + 1, k));
			ans %= mod;
			if (ans < 0) ans += mod;
			write(ans);
			putc('\n');
		} else {
		// 因此我们把这个 k 比较小的这个直接用数组存起来，后面直接输出即可
			ll ans = 0;
			ans = F[N][k] - (x - k < 0 ? 1 : F[x - k][k]) * (N - x - k + 1 < 0 ? 1 : F[N - x - k + 1][k]);
			ans %= mod;
			if (ans < 0) ans += mod;
			write(ans);
			putc('\n');
		}
	}
}

AC代码

AC
https://acm.hdu.edu.cn/contest/view-code?cid=1236&rid=7030

源代码

// teamname: Gospel_rock
/**
 * Problem: 太近就不合法了
 * Contest: 
 * Judge: HDOJ
 * URL: https://acm.hdu.edu.cn/contest/problem?cid=1236&pid=1003
 * Created: 2026-08-13 13:22:28
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(), vec.end()
#define lson(o) (o << 1)
#define rson(o) (o << 1 | 1)
#define SZ(a) ((long long)a.size())
#define fsp(x) fixed << setprecision(x)
#define debug(x) cerr << "[" << #x << "]" << ": " << x << "\n"
#define cend cerr << "\n---------------------------------------------------\n"
#define cEnd cerr << "\n***************************************************\n"

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
// 不用 M_PI: 后者是 POSIX 扩展, glibc <cmath> 严格模式会 undef
const long double PI = acosl(-1.0);

ll lT, testcase;

/*
 *
 */

// 来自wida github仓库 https://github.com/hh2048/XCPC/tree/main 加了一些新功能
//46 ms https://acm.hdu.edu.cn/contest/view-code?cid=1179&rid=14912 读入字符getc(a) 的AC记录
// AC https://vjudge.net/solution/63197697 一道测试读写的codechef题目
namespace QuickRead {
	// 快读
	char buf[1 << 21], *p1 = buf, *p2 = buf;

	inline int getc() {
		return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
	}

	template<typename T>
	void Cin(T &a) {
		T ans = 0;
		bool f = 0;
		char c = getc();
		for (; c < '0' || c > '9'; c = getc()) {
			if (c == '-') f = 1;
		}
		for (; c >= '0' && c <= '9'; c = getc()) {
			ans = ans * 10 + c - '0';
		}
		a = f ? -ans : ans;
	}

	void getc(char &a) {
		char c = getc();
		while (isspace(c)) {
			c = getc();
		}
		a = c;
	}

	template<typename T, typename... Args>
	void Cin(T &a, Args &... args) {
		Cin(a), Cin(args...);
	}

	// ===== 输出 =====
	static constexpr size_t OUT_CAP = 1 << 21; // 大概是2MB
	char obuf[OUT_CAP];
	size_t op = 0;

	inline void flush() {
		if (op) {
			fwrite(obuf, 1, op, stdout);
			op = 0;
		}
	}

	inline void putc(char c) {
		if (op == OUT_CAP) flush();
		obuf[op++] = c;
	}

	template<typename T>
	void write(T x) {
		// 注意，这里输出不带换行
		if (x < 0) putc('-'), x = -x;
		if (x > 9) write(x / 10);
		putc(x % 10 + '0');
	}

	struct Flusher {
		// 析构时自动刷新
		~Flusher() { flush(); }
	} flusher;
} // namespace QuickRead
using namespace QuickRead;


namespace Comb {
	// 组合数加逆元，依赖于这个MAXN（初始化）
	vector<ll> frac, infrac;
	int ln = 1;
	bool initialized = false;
	// 在 k=0或者更小的时候 return 1
	inline ll binpow(ll a, ll k) {
		ll res = 1;
		a %= mod;
		while (k > 0) {
			if (k & 1) res = (res * a) % mod;
			a = (a * a) % mod;
			k >>= 1;
		}
		return res;
	}

	void Comb(int n) {
		ln = n;
		frac.assign(n + 5, 1);
		infrac.assign(n + 5, 1);
		for (int i = 1; i <= ln; ++i) {
			frac[i] = (frac[i - 1] * i) % mod;
		}
		infrac[ln] = binpow(frac[ln], mod - 2);
		for (int i = ln - 1; i >= 0; --i) {
			infrac[i] = (infrac[i + 1] * (i + 1)) % mod;
		}
	}

	inline ll CC(ll n, ll k) {
		if (k < 0 || k > n) {
#ifdef LOCAL
			cerr << "CC 组合数传入参数不合法，可能是传入顺序错了\n";
#endif
			return 0; // Return 0 if k is out of range [0, n]
		}
		if (!initialized) {
			Comb(MAXN);
			initialized = true;
		}
		ll res = frac[n];
		res = (res * infrac[n - k]) % mod;
		res = (res * infrac[k]) % mod;
		return res;
	}

	inline ll PP(ll n, ll k) {
		if (k < 0 || k > n) {
#ifdef LOCAL
			cerr << "PP 排列数传入参数不合法，可能是传入顺序错了\n";
#endif
			return 0;
		}
		if (!initialized) {
			Comb(MAXN);
			initialized = true;
		}
		ll res = frac[n] * infrac[n - k];
		res %= mod;
		return res;
	}
}

using namespace Comb;


ll N, Q;

constexpr ll SQRT = 200;

ll f_cal(ll m, ll k) {
	ll ans = 0;
	ll up = (m + k - 1) / k;
	for (int c = 0; c <= up; ++c) {
		ans += CC(m - (c - 1) * (k - 1), c);
		ans %= mod;
	}
	ans %= mod;
	if (ans < 0) ans += mod;
	return ans;
}

void Solve() {
	Cin(N, Q);
	map<ll, vector<ll> > mp;
	vector<vector<ll> > F(N + 2, vector<ll>(min(N, SQRT) + 2));
	for (int k = 1; k <= min(N, SQRT); ++k) {
		F[0][k] = 1;
		for (int i = 1; i <= N; ++i) {
			F[i][k] = F[i - 1][k] + (i - k < 0 ? 1 : F[i - k][k]);
			F[i][k] %= mod;
		}
	}
	for (int _ = 1; _ <= Q; ++_) {
		ll x, k;
		Cin(x, k);
		ll up = (N + k - 1) / k;
		if (k > SQRT) {
			ll ans = f_cal(N, k) - (x - k < 0 ? 1 : f_cal(x - k, k)) * (
				         N - x - k + 1 < 0 ? 1 : f_cal(N - x - k + 1, k));
			ans %= mod;
			if (ans < 0) ans += mod;
			write(ans);
			putc('\n');
		} else {
			ll ans = 0;
			ans = F[N][k] - (x - k < 0 ? 1 : F[x - k][k]) * (N - x - k + 1 < 0 ? 1 : F[N - x - k + 1][k]);
			ans %= mod;
			if (ans < 0) ans += mod;
			write(ans);
			putc('\n');
		}
	}
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
#ifdef LOCAL
	cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif

	Cin(lT);
	for (testcase = 1; testcase <= lT; ++testcase)
		Solve();
	return 0;
}

/*
AC
https://acm.hdu.edu.cn/contest/view-code?cid=1236&rid=7030

*/

心路历程（WA，TLE，MLE……）