Chessboard

题目链接

题意

你可以随意挑一个正方形，设大小$k \times k$的，在每个位置放入不少于$m$个球，现在要任意挑$k$个不在同一行且不在同一列的格子，他们的球数和都是相等的不大于$N$的数字，问方案数。

思路

答案要求$\sum_{k=1}^{N} \sum_{T=1}^{N} f_{m}(k, T).$
其中$f_{m}(k, T)$表示在大小为$k$的方格内放入不少于$m$个球，和都是$T$。
发现$f_{m}{k, T} = f_{0}(k, T-km)$，记为$f(k, T-km)$.
满足要求的放置方案是这样的：$\sum_{i} a_{i} + \sum_{j} b_{j} = T. a_{i}$指在第$i$行整行都放入$a_{i}$个球，$b_{j}$指在第$j$列整列都放入$b_{j}$个球。
这就变成了将$T$分成$2k$个数的和，方案数是$C_{T-2k-1}^{2k-1}$。
但其实我们算重复了，为什么呢？
一些$a_{i}$可以再减1，$b_{j}$再加1的方案，其实已经算过了，但我们又算了一次。
所以减去这部分，有$f(k, T) = C_{T-2k-1}^{2k-1} - C_{T-k-1}^{k-1}.$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#ifndef ONLINE_JUDGE
#define dbg(x...) do{cout << "\033[33;1m" << #x << "->" ; err(x);} while (0)
void err(){cout << "\033[39;0m" << endl;}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x){for (auto v: a) cout << v << ' '; err(x...);}
template<typename T, typename... A>
void err(T a, A... x){cout << a << ' '; err(x...);}
#else
#define dbg(...)
#endif
#define inf 1ll << 50

const ll mod = 998244353;
const ll N = 6e3 + 5;
ll fac[N];

ll Pow(ll a, ll b) {
	ll ans = 1;
	while (b) {
		if (b & 1)
			ans = a * ans % mod;
		b >>= 1;
		a = a * a % mod;
	}
	return ans;
}

ll C(ll n, ll m) {
	return fac[n] * Pow(fac[m] * fac[n - m] % mod, mod - 2) % mod;
}

int main() {
	int T;
	scanf("%d", &T);
	fac[0] = 1;
	for (int i = 1; i <= 6000; i++)
		fac[i] = fac[i - 1] * 1ll * i % mod;
	while (T--) {
		int n, m;
		scanf("%d%d", &n, &m);
		ll ans = 0;
		for (int k = 1; k * m <= n; k++)
			for (int t = m * k; t <= n; t++) {
				int tt = t - m * k;
				ll tmp = C(tt + 2 * k - 1, 2 * k - 1);
				if (tt >= k)
					tmp -= C(tt + k - 1, 2 * k - 1);
				tmp = (tmp + mod) % mod;
				ans = (ans + tmp) % mod;
			}
		printf("%lld\n", ans);
	}
	return 0;
}