OI - CSP2019模拟赛 B | Lucky_Glass's Blog

以心为名，名为爱惜

0%

OI - CSP2019模拟赛 B

发表于 更新于 分类于 Valine：

这个难度梯度未免也太大了……

Part1. 题面

你需要给一个 $n\times n$ 的方格图染黑白两色，需要满足：

  1. 没有一整行的颜色相同；
  2. 没有一整列的颜色相同；
  3. $n\times n$ 的正方形的主对角线（左上到右下）的颜色不同；
  4. $n\times n$ 的正方形的从对角线（左下到右上）的颜色不同；

求有多少种染色方案，模 $998244353$。

数据规模：$1\le n\le300$。

Part2. 解析

这种方格染色题见得很多了……

Part2/1. 假如不考虑对角线

如果这道题不要求对角线不相同，其实就非常简单的一个容斥原理—— $f_{i,j}$ 表示至少 $i$ 行、至少 $j$ 列的颜色相同，不难得出：

$C_n^i\times C_n^j$ 就是从 $n$ 行 $n$ 列中选出这 $i$ 行 $j$ 列；$2^{(n-i)(n-j)}$ 中，$(n-i)(n-j)$ 计算了不在这 $i$ 行 $j$ 列中的格子的数量，这些格子不受限制，可以填黑白两色，所以是 $2$ 的幂；

当 $i=j=0$ 时，这 $i$ 行 $j$ 列只有一种涂色方法，即不涂；
当 $i=0,j\not=0$ 时，这 $j$ 列每一列都可以涂成黑白两色（互不影响），所以是 $2^j$；当 $i\not=0,j=0$ 时，同理；
当 $i\not=0,j\not=0$ 时，因为行列有交叉，所以这 $i$ 行和 $j$ 列颜色必须完全相同，所以只能涂成黑白两色，方案数为 $2$。

然后再简单容斥一下：

但是我们得到的 $ans_0$ 是没有考虑对角线不合法的情况的。直接计算对角线不合法的总方案数仍然不方便，我们还要容斥！设 $ans_1$ 是有至少 $1$ 条对角线颜色相同的方案数，$ans_2$ 是 $2$ 条对角线颜色都相同的方案数。

不难发现，“主对角线颜色相同”的方案数 和 “从对角线颜色相同”的方案数 是一样的（旋转一下就好了）。

所以最后答案应该是 $ans_0-2ans_1+ans_2$。

接下来就是要计算 $ans_1$ 和 $ans_2$ 了。

Part2/2. 至少有一条对角线颜色相同

不妨设是从左上到右下的主对角线颜色相同，于是整行整列如果颜色要相同，就只能选和对角线颜色相同的颜色了。于是就有两种做法。

Part2/2/1. 直接容斥

仍然可以容斥。但是如果仍然只枚举 $i$ 行 $j$ 列，难点在于计算有多少个点是可以随便乱选的（因为除了你选的 $i$ 行 $j$ 列，还有一条对角线的颜色是有限制的）。

因此可以在多加一维枚举——枚举 $k=1\to n$ ，表示所选的 $i$ 行 $j$ 列中有 $k$ 对行列是 交叉在对角线上 的，那么剩下的 $(i-k)$ 行 $(j-k)$ 列一定分别覆盖了一些对角线上的点，这样的话就可以知道对角线上被所选的 $i$ 行 $j$ 列覆盖的点有 $(i+j-k)$ 个，从而可以计算有多少个点是被限制的。

其他的和最开始的容斥是一样的，但是实际计算的时候我是先枚举 $k$ ，然后枚举 $(i+k)$ 行 $(j+k)$ 列颜色相同。

其中指数 $n-k-i-j$ 是计算对角线上未被选择的 $(i+k)$ 行 $(j+k)$ 列覆盖的对角线上的格子的个数；$(n-i-k)(n-j-k)$ 计算的是选择的 $(i+k)$ 行 $(j+k)$ 列覆盖的格子的个数。合起来就是所有被限制染色的格子的个数。

Part2/2/2. 动态规划

我们希望能这样容斥：

容斥的难点在计算方案数 $f_{i,j}$，于是可以用 DP 计算方案数。

我们考虑依次决定第 $k$ 行是否颜色相同、第 $k$ 列是否颜色相同，于是有了一个比较简明的 dp 定义式 dp[i][j][k] 表示“前 $k$ 行中至少有 $i$ 行颜色相同，前 $k$ 列中至少有 $j$ 列颜色相同”的方案数。

dp[i][j][k] 的转移其实就是考虑第 $k$ 行是否颜色一样以及第 $k$ 列是否颜色一样。那么就有下面 $4$ 种转移：

  1. 第 $k$ 行和第 $k$ 列不作限制：那么第 $k$ 行、第 $k$ 列上就只有 $(k,k)$ 这个在对角线上的格子是被限制只能选一种颜色的，但是我们计算的时候并不知道这个格子被限制（这个格子在计算时会算作没有限制，从而得到正确答案的两倍），所以在这里 预先把答案除以二，因为是模运算，应该乘逆元。

    即 dp[i][j][k]+=dp[i][j][k-1]*inv2

  2. 限制第 $k$ 行颜色一定相同：那么对角线上的格子也被限制了，只能选择一种颜色，所以不会有问题。

    直接加方案数就好了 dp[i][j][k]+=dp[i-1][j][k-1]

  3. 限制第 $k$ 列颜色一定相同：和 2. 一样……

    dp[i][j][k]+=dp[i][j-1][k-1]

  4. 同时限制行和列：同样，对角线上也被限制了，也不会有问题

    dp[i][j][k]+=dp[i-1][j-1][k-1]

最后算出来 $f_{i,j}$ 就是 2*dp[i][j][n] （因为对角线可以有两种颜色）。

Part2/3. 两条对角线颜色分别相同

如果还要用容斥的话，就要分别枚举两条对角线的覆盖情况，变成 $O(n^4)$ 了，过不了。所以只能 DP，我们仍然希望能够这样计算：

需要分 $n$ 的奇偶讨论了……因为如果 $n$ 是奇数，则两条对角线有相交的格子，必须颜色相同；如果 $n$ 是偶数，则两条对角线无相交的格子，颜色可以不同。

先说比较简单的，当 $n$ 为偶数且两条对角线颜色不一样。那么显然不可能有一整行、一整列颜色相同了，除了对角线，其他的 $(n-2)n$ 个格子都可以乱选，方案数为 $2\times2^{n(n-2)}$，乘二是因为对角线选择方案有两种。

然后就要计算两条对角线颜色都相同的方案数了。因为这种情况下 $n$ 奇数偶数其实差不多，就假设 $n$ 是奇数。

直观上感觉有两条对角线的情况下，中间是比较特殊的……所以从中间开始转移。dp[i][j][k] 表示最中间的 $k$ 行 $k$ 列中，至少有 $i$ 行 $j$ 列的颜色相同的方案数。转移就要同时考虑 向外扩展一层，并决定是否限制扩展出去的两行、两列颜色相同。如下图，黄色块就是要决定是否要限制的行和列，深色是对角线，也需要限制。

1571811036251

  1. 不作限制，也就是从 dp[i][j][k-2] 转移；但是对角线上的四个格子仍然有限制，所以要除以 $2^4$，仍然乘逆元；
  2. 限制 1 列，从 dp[i][j-1][k-2] 转移，还有两个对角线上的格子，除以 $2^2$；
  3. 限制 2 列，从 dp[i][j-2][k-2] 转移，都满足限制；
  4. 限制 1 行，从 dp[i-1][j][k-2] 转移，除了该行，还有两个对角线上的格子，除以 $2^2$；
  5. 限制 1 行 1 列，从 dp[i-1][j-1][k-2] 转移，除此之外还有一个对角线上的格子，除以 $2$；
  6. 限制 1 行 2 列，从 dp[i-1][j-2][k-2] 转移，都满足限制；
  7. 限制 2 行，从 dp[i-2][j][k-2] 转移，都满足限制；
  8. 限制 2 行 1 列，从 dp[i-2][j-1][k-2] 转移，都满足限制；
  9. 限制 2 行 2 列，从 dp[i-2][j-2][k-2] 转移，都满足限制；

再进行容斥就行了。

Part3. 源代码

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
/*Unlucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int MOD=998244353;

typedef long long ll;
const int N=300;

struct NUMBER{
	int num;
	NUMBER(){}
	NUMBER(int x){num=x;}
	NUMBER operator +(const NUMBER &B)const&{return int(((1ll*num+B.num)%MOD+MOD)%MOD);}
	NUMBER operator -(const NUMBER &B)const&{return int(((1ll*num-B.num)%MOD+MOD)%MOD);}
	NUMBER operator *(const NUMBER &B)const&{return int(((1ll*num*B.num)%MOD+MOD)%MOD);}
	NUMBER operator +=(const NUMBER &B){return (*this)=(*this)+B;}
	NUMBER operator -=(const NUMBER &B){return (*this)=(*this)-B;}
	NUMBER operator *=(const NUMBER &B){return (*this)=(*this)*B;}
}fac[N*2+3],inv[N*2+3],dp[N+3][N+3][5],inv2;

int n;

NUMBER QPow(NUMBER A,int B){
	NUMBER res(1);
	while(B){
		if(B&1) res*=A;
		A*=A;
		B>>=1;
	}
	return res;
}
NUMBER fC(int A,int B){return fac[B]*inv[A]*inv[B-A];}
int main(){
	/*Prepare*/
	fac[0]=1;
	for(int i=1;i<=N*2;i++) fac[i]=fac[i-1]*i;
	inv[N*2]=QPow(fac[N*2],MOD-2);
	for(int i=N*2-1;i>=0;i--) inv[i]=inv[i+1]*(i+1);
	inv2=QPow(2,MOD-2);
	
	/*Read in*/
	scanf("%d",&n);
	
	/*Part1*/
	NUMBER all(0);
	for(int i=0;i<=n;i++)
		for(int j=0;j<=n;j++){
			NUMBER val=fC(i,n)*fC(j,n)*QPow(2,(n-i)*(n-j));
			if(!i &&  j) val*=QPow(2,j);
			if( i && !j) val*=QPow(2,i);
			if( i &&  j) val*=2;
			if((i+j)%2) all-=val;
			else all+=val;
		}
	
	/*Part2*/
	dp[0][0][0]=1;
	for(int _k=1;_k<=n;_k++){
		int k=_k&1;
		for(int i=0;i<=_k;i++)
			for(int j=0;j<=_k;j++){
				NUMBER &now=dp[i][j][k];
				now=0;
				now+=dp[i][j][!k]*inv2;
				if(i) now+=dp[i-1][j][!k];
				if(j) now+=dp[i][j-1][!k];
				if(i && j) now+=dp[i-1][j-1][!k];
			}
	}
	NUMBER mnu(0);
	for(int i=0;i<=n;i++)
		for(int j=0;j<=n;j++)
			if((i+j)%2) mnu-=dp[i][j][n&1]*QPow(2,(n-i)*(n-j));
			else mnu+=dp[i][j][n&1]*QPow(2,(n-i)*(n-j));
	mnu*=4;
	
	/*Part3*/
	memset(dp,0,sizeof dp);
	if(n%2){
		dp[0][0][0]=inv2;dp[0][1][0]=1;
		dp[1][0][0]=1;dp[1][1][0]=1;
		for(int _k=3;_k<=n;_k+=2){
			int k=(_k/2)&1;
			for(int i=0;i<=_k;i++)
				for(int j=0;j<=_k;j++){
					NUMBER &now=dp[i][j][k];
					now=0;
					if(i>=0 && j>=0) now+=dp[i][j][!k]*QPow(inv2,4);
					if(i>=0 && j>=1) now+=dp[i][j-1][!k]*QPow(inv2,2)*2;
					if(i>=0 && j>=2) now+=dp[i][j-2][!k];
					if(i>=1 && j>=0) now+=dp[i-1][j][!k]*QPow(inv2,2)*2;
					if(i>=1 && j>=1) now+=dp[i-1][j-1][!k]*inv2*4;
					if(i>=1 && j>=2) now+=dp[i-1][j-2][!k]*2;
					if(i>=2 && j>=0) now+=dp[i-2][j][!k];
					if(i>=2 && j>=1) now+=dp[i-2][j-1][!k]*2;
					if(i>=2 && j>=2) now+=dp[i-2][j-2][!k];
				}
		}
	}
	else{
		dp[0][0][1]=QPow(inv2,4);dp[0][1][1]=QPow(inv2,2)*2;dp[0][2][1]=1;
		dp[1][0][1]=QPow(inv2,2)*2;dp[1][1][1]=inv2*4;dp[1][2][1]=2;
		dp[2][0][1]=1;dp[2][1][1]=2;dp[2][2][1]=1;
		for(int _k=4;_k<=n;_k+=2){
			int k=(_k/2)&1;
			for(int i=0;i<=_k;i++)
				for(int j=0;j<=_k;j++){
					NUMBER &now=dp[i][j][k];
					now=0;
					if(i>=0 && j>=0) now+=dp[i][j][!k]*QPow(inv2,4);
					if(i>=0 && j>=1) now+=dp[i][j-1][!k]*QPow(inv2,2)*2;
					if(i>=0 && j>=2) now+=dp[i][j-2][!k];
					if(i>=1 && j>=0) now+=dp[i-1][j][!k]*QPow(inv2,2)*2;
					if(i>=1 && j>=1) now+=dp[i-1][j-1][!k]*inv2*4;
					if(i>=1 && j>=2) now+=dp[i-1][j-2][!k]*2;
					if(i>=2 && j>=0) now+=dp[i-2][j][!k];
					if(i>=2 && j>=1) now+=dp[i-2][j-1][!k]*2;
					if(i>=2 && j>=2) now+=dp[i-2][j-2][!k];
				}
		}
	}
	NUMBER add(0);
	for(int i=0;i<=n;i++)
		for(int j=0;j<=n;j++)
			if((i+j)%2) add-=dp[i][j][(n/2)&1]*QPow(2,(n-i)*(n-j));
			else add+=dp[i][j][(n/2)&1]*QPow(2,(n-i)*(n-j));
	if(n%2) add*=2;
	else add=(add+QPow(2,n*(n-2)))*2;
	
	NUMBER ans=all-mnu+add;
	printf("%d\n",ans.num);
	return 0;
}

The End

Thanks for reading!

Email: lucky_glass@foxmail.com，欢迎提问？（虽然我知道肯定没有人）