题解 | #Floor Tiles in a Park#

【大意】

给定 $W\times HW\backslash times\; H$ 的矩形，要恰好划分为 $kk$ 个小矩形的方案数。

【分析】

考虑极限情况是 $k=5k=5$ ，此时会有贡献 $\left({\displaystyle \genfrac{}{}{0px}{}{n-1}{k-1}}\right)\backslash dbinom\; \{n-1\}\; \{k-1\}$ 和 $\left({\displaystyle \genfrac{}{}{0px}{}{m-1}{k-1}}\right)\backslash dbinom\; \{m-1\}\; \{k-1\}$ ；故表达式是一个不超过 $44$ 次的表达式，因此答案可以由拉格朗日插值法表达

考虑令 ${\displaystyle l_k(x)=\prod _{i\mathrm{\ne }k}\frac{x-k}{i-k}}\backslash displaystyle\; l\_k(x)=\backslash prod\_\{i\backslash neq\; k\}\{x-k\backslash over\; i-k\}$ ，则 ${\displaystyle F(x)=\sum _{i=0}^5\sum _{j=0}^5{v}_{i,j}\cdot l_i(x)\cdot l_j(y)}\backslash displaystyle\; F(x)=\backslash sum\_\{i=0\}^5\backslash sum\_\{j=0\}^5\; v\_\{i,\; j\}\backslash cdot\; l\_i(x)\backslash cdot\; l\_j(y)$

其中 $v_{i,j}v\_\{i,\; j\}$ 表示 $i\times ji\backslash times\; j$ 大小的矩形的答案

因此可以写一个暴力将答案打出来，然后用拉格朗日插值法直接插出系数

最后直接把系数表交上去即可

【打表代码】

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define de(x) cout << #x <<" = "<<x<<endl
#define dd(x) cout << #x <<" = "<<x<<" "
const int P=998244353;
ll w, h, k;
bool vis[6][6];
inline bool allVised(ll x, ll y) {
	for(int i=1; i<=x; ++i)
		for(int j=1; j<=y; ++j)
			if(!vis[i][j])
				return 0;
	return 1;
}
inline void draw(int x, int y, int p, int q, bool v) {
	for(int i=x; i<=p; ++i)
		for(int j=y; j<=q; ++j)
			vis[i][j]=v;
}
inline bool allEmpty(int x, int y, int p, int q) {
	for(int i=x; i<=p; ++i)
		for(int j=y; j<=q; ++j)
			if(vis[i][j])
				return 0;
	return 1;
}
ll dfs(ll x, ll y, ll k) {
	if(k==0)
		return allVised(x, y);
	ll res=0;
	for(int i=1; i<=x; ++i)
		for(int j=1; j<=y; ++j) if(!vis[i][j]) {
			for(int p=i; p<=x; ++p)
				for(int q=j; q<=y; ++q) if(!vis[p][q])
					if(allEmpty(i, j, p, q)) {
						draw(i, j, p, q, 1);
						res+=dfs(x, y, k-1);
						draw(i, j, p, q, 0);
					}
		}
	return res;
}
inline ll work(ll x, ll y) {
	for(int i=1; i<=x; ++i)
		for(int j=1; j<=y; ++j)
			vis[i][j]=0;
	return dfs(x, y, k);
}
ll A[6][6], lx[6][6];
inline ll kpow(ll a, ll x) { ll ans=1; for(;x;x>>=1, a=(ll)a*a%P) if(x&1) ans=(ll)ans*a%P; return ans; }
inline ll ans(ll x, ll y) {
	ll res=0;
	x%=P; y%=P;
	for(int i=0, xi=1; i<=5; ++i, xi=xi*x%P)
		for(int j=0, yj=1; j<=5; ++j, yj=yj*y%P)
			res=(res+xi*yj*A[i][j])%P;
	return res<0?res+P:res;
}
inline void init() {
	for(int i=1; i<=5; ++i) {
		ll *l=lx[i];
		l[0]=1;
		for(int j=1; j<=5; ++j) if(j!=i) {
			for(int k=5; k>=1; --k)
				l[k]=(l[k-1]-j*l[k])%P;
			l[0]=-j*l[0]%P;
		}
		
		ll res=0;
		for(int j=5; ~j; --j) res=(res*i+l[j])%P;
		res=kpow(res, P-2);
		for(int j=0; j<=5; ++j) l[j]=l[j]*res%P;
	}
	
	ll res[6][6]={0};
	for(int i=1; i<=5; ++i)
		for(int j=1; j<=5; ++j) {
			ll B[6][6]={0};
			for(int p=0; p<=5; ++p)
				for(int q=0; q<=5; ++q)
					B[p][q]=lx[i][p]*lx[j][q]%P;
//			ll v=work(i, j);
			ll v=0;
			if(i>j) v=res[j][i];
			else v=work(i, j);
			res[i][j]=v;
			for(int i=1; i<=k; ++i) assert(v%i==0), v/=i;
			dd(i), dd(j), de(v);
			for(int p=0; p<=5; ++p)
				for(int q=0; q<=5; ++q)
					A[p][q]=(A[p][q]+v*B[p][q])%P;
		}
	
	cout<<endl<<endl<<"\t{";
	for(int i=0; i<=5; ++i) {
		cout<<endl<<"\t\t{"<<A[i][0];
		for(int j=1; j<=5; ++j)
			cout<<","<<A[i][j];
		cout<<"}";
		if(i!=5) cout<<",";
	}
	cout<<endl<<"\t}"<<endl;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>w>>h>>k;
	init();
	cout<<ans(w, h);
	cout.flush();
	return 0;
}

实测 $99$ s 能跑出 $k=4k=4$ 的答案；$300+300+$ s 能跑出 $k=5k=5$ 的代码

【提交代码】

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define de(x) cout << #x <<" = "<<x<<endl
#define dd(x) cout << #x <<" = "<<x<<" "
const int P=998244353;
ll w, h, k;
ll A[6][6][6]={
	{
		{0,0,0,0,0,0},
		{0,0,0,0,0,0},
		{0,0,0,0,0,0},
		{0,0,0,0,0,0},
		{0,0,0,0,0,0},
		{0,0,0,0,0,0}
	},
	{
		{1,0,0,0,0,0},
		{0,0,0,0,0,0},
		{0,0,0,0,0,0},
		{0,0,0,0,0,0},
		{0,0,0,0,0,0},
		{0,0,0,0,0,0}
	},
	{
		{-2,-998244352,0,0,0,0},
		{-998244352,0,0,0,0,0},
		{0,0,0,0,0,0},
		{0,0,0,0,0,0},
		{0,0,0,0,0,0},
		{0,0,0,0,0,0}
	},
	{
		{6,-499122182,499122177,0,0,0},
		{-499122182,4,0,0,0,0},
		{499122177,0,0,0,0,0},
		{0,0,0,0,0,0},
		{0,0,0,0,0,0},
		{0,0,0,0,0,0}
	},
	{
		{-23,-665496207,499122170,-831870294,0,0},
		{-665496207,998244321,-499122171,0,0,0},
		{499122170,-499122171,0,0,0,0},
		{-831870294,0,0,0,0,0},
		{0,0,0,0,0,0},
		{0,0,0,0,0,0}
	},
	{
		{104,-748683419,707089806,-249561093,291154603,0},
		{-748683419,332748336,-499122247,332748122,0,0},
		{707089806,-499122247,16,0,0,0},
		{-249561093,332748122,0,0,0,0},
		{291154603,0,0,0,0,0},
		{0,0,0,0,0,0}
	}
};
inline ll kpow(ll a, ll x) { ll ans=1; for(;x;x>>=1, a=(ll)a*a%P) if(x&1) ans=(ll)ans*a%P; return ans; }
inline ll ans(ll x, ll y, ll k) {
	ll res=0;
	auto a=A[k];
	x%=P; y%=P;
	for(int i=0, xi=1; i<=5; ++i, xi=xi*x%P)
		for(int j=0, yj=1; j<=5; ++j, yj=yj*y%P)
			res=(res+(ll)xi*yj%P*a[i][j])%P;
	return res<0?res+P:res;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>w>>h>>k;
	cout<<ans(w, h, k);
	cout.flush();
	return 0;
}