A题: Floor Tiles in a Park

原题链接:https://ac.nowcoder.com/acm/contest/33192/A

题目大意

给定大小为 $W\times H(1\le W,H\le 10^9)$ 的矩形，求其恰好分割为 $K(1\le k\le min(5,W\times H))$ 个长宽均为整数的子矩形的方案数。

题解

$k$ 的范围很小，可以手玩枚举算出每种情况计算答案。

在手玩的过程中，我们可以发现答案由若干组合数构成，且组合数最复杂为 $C_x^4$ 的形式。
因此，我们一定可以将答案展开为如下形式:
$$ans=\sum _{i=0}^4\sum _{j=0}^4{a}_{i\times 5+j}{W}^i{H}^j$$

不妨在本地对于每一个 $k\in [1,5]$ 搜索出 $H,W\le 5$ 的 $25$ 种情况，作插值求出此时的系数 $a_{i,j}$ 并打表。当读入 $H,W,k$ 时代入求解即可。
搜索可以每次枚举填充一个空的子矩形，在 $k$ 次填充后判断是否填满即可。
作插值可以用高斯消元解同余方程组，复杂度为 $O(25^3)$ 显然可行(而且是本地跑)。



本地测试打表时间在400s+左右(含高斯消元计算时间)。

参考代码

打表代码:

#include
using namespace std;

template<class T>inline void read(T&x){
	char c,last=' ';
	while(!isdigit(c=getchar()))last=c;
	x=c^48;
	while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+(c^48);
	if(last=='-')x=-x;
}

const int MAXN=7,P=998244353;
int n,m,k;
long long ans;
int b[MAXN][MAXN];

bool isEmpty(int x1,int y1,int x2,int y2){//判断子矩阵是否为空
	for(int i=x1;i<=x2;++i){
		for(int j=y1;j<=y2;++j){
			if(b[i][j])return false;
		}
	}
	return true;
}

bool isFull(){//判断是否填满
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			if(!b[i][j])return false;
		}
	}
	return true;
}

void be(int x1,int y1,int x2,int y2,int c){//子矩形赋值(填充/清空)
	for(int i=x1;i<=x2;++i){
		for(int j=y1;j<=y2;++j){
			b[i][j]=c;
		}
	}
}

void dfs(int x){
	if(x>k){
		if(isFull())++ans;
		return;
	}
	for(int x1=1;x1<=n;++x1){
		for(int y1=1;y1<=m;++y1){
			for(int x2=x1;x2<=n;++x2){
				for(int y2=y1;y2<=m;++y2){
//					if(x==1&&n>=4&&m>=4)cerr<
					if(isEmpty(x1,y1,x2,y2)){//如果是空子矩形则尝试填充
						be(x1,y1,x2,y2,1);//填充
						dfs(x+1);
						be(x1,y1,x2,y2,0);//回溯
					}
				}
			}
		}
	}
}

#define ll long long

ll qpow(ll x,ll p){//快速幂(求逆元用)
	ll ret=1;
	for(;p;x=x*x%P,p>>=1)if(p&1)ret=ret*x%P;
	return ret;
}

ll inv(ll x){return qpow(x,P-2);}//逆元

int N=25;
ll a[MAXN*MAXN][MAXN*MAXN],x[MAXN*MAXN];//高斯消元矩阵&解(下标从0开始)

void print(){//输出矩阵(调试用)
	for(int i=1;i<N;++i){
		for(int j=1;j<=N;++j){
			cout<<a[i][j]<<" \n"[j==N];
		}
	}
	puts("");
}

void Gauss(){//高斯消元求解同余方程组
	int row=0,col=0;
	for(int maxrow;row<N&&col<N;++row,++col){
		maxrow=row;
		for(int i=row;i<N;++i)if(abs(a[i][col])>abs(a[maxrow][col]))maxrow=i;
		if(maxrow!=row)for(int j=col;j<=N;++j)swap(a[maxrow][j],a[row][j]);
		for(int i=row+1;i<N;++i){
			if(!a[i][col])continue;
			ll tmp=a[i][col]*inv(a[row][col])%P;//将除法改为逆元
			for(int j=col;j<=N;++j)a[i][j]-=a[row][j]*tmp,a[i][j]%=P;
		}
//		print();
	}
	for(int i=N-1;i>=0;--i){
		x[i]=a[i][N];
		for(int j=i+1;j<N;++j)x[i]-=a[i][j]*x[j],x[i]%=P;
		x[i]*=inv(a[i][i]),x[i]%=P;//将除法改成逆元
	}
}

int main()
{
	read(k);
	for(n=1;n<=5;++n){
		for(m=n;m<=5;++m){
//			cerr<
			ans=0;
			dfs(1);
			for(int i=1;i<=k;++i)ans/=i;//分为k个子矩形的方案会被重复计算k!次
			ans%=P;//取模
			for(int i=0,x=1;i<=4;++i,x*=n){
				for(int j=0,y=1;j<=4;++j,y*=m){
					a[(n-1)*5+m][i*5+j]=x*y;//记录方程
				}
			}
			a[(n-1)*5+m][25]=ans;
			swap(n,m);//一个小优化H=n,W=m与W=m,H=n是对称的,不用重复求解
			for(int i=0,x=1;i<=4;++i,x*=n){
				for(int j=0,y=1;j<=4;++j,y*=m){
					a[(n-1)*5+m][i*5+j]=x*y%P;
				}
			}
			a[(n-1)*5+m][25]=ans;
			swap(n,m);//记得换回去
		}
	}
//	print();
	Gauss();
	cout<<"{";
	for(int i=0;i<N;++i){//输出系数,注意格式方便复制
		cout<<x[i]<<",}"[i==N-1];
	}
	puts("");
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140

提交代码:

#include
using namespace std;

template<class T>inline void read(T&x){
	char c,last=' ';
	while(!isdigit(c=getchar()))last=c;
	x=c^48;
	while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+(c^48);
	if(last=='-')x=-x;
}

const int P=998244353;
int a[7][37]={//系数表
	{},
	{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},
	{-2,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
	{6,499122171,499122177,0,0,-499122182,-998244349,0,0,0,499122177,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
	{-23,-665496207,499122170,166374059,0,-665496207,-32,-499122171,0,0,-499122183,499122182,0,0,0,166374059,0,0,0,0,0,0,0,0,0},
	{104,-748683419,707089806,-249561093,291154603,249560934,332748336,499122106,332748122,0,707089806,-499122247,-998244337,0,0,748683260,332748122,0,0,0,-707089750,0,0,0,0}
};

int main()
{
	int n,m,k;
	read(n),read(m),read(k);
	int ans=0;
	for(int i=0,x=1;i<=4;++i,x=1ll*x*n%P){
		for(int j=0,y=1;j<=4;++j,y=1ll*y*m%P){
			ans=(ans+1ll*a[k][i*5+j]*x%P*y)%P;//代入计算
		}
	}
	cout<<(ans+P)%P<<'\n';//因为系数表中有负数,所以ans也可能为负数,注意转为正数
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34