隐藏
「BJOI2017」机动训练 - 容斥原理+动态规划 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

「BJOI2017」机动训练 - 容斥原理+动态规划

题目大意

    询问一个棋盘上所有路径形成字符串的等价类包含的数目平方和,在指定了起点与终点后,路径一定不能不朝着终点的方向移动。
    棋盘是八连通的。


题目分析

神题。
首先进行一步转化:

对平方的处理:转化为棋盘上两个人合法的走路,路径字符串相同的对数。

继续进行转化,若同时指定起点与终点效率会变低。
根据允许移动方向的性质,不妨将移动的方向分为四类。

  1. 向右上方走
  2. 向右下方走
  3. 向左下方走
  4. 向左上方走

在指定了两人的起点后,再指定两人的方向,这样就不需要枚举终点了,然后我们进行Dp:

设置状态$f[x_1,y_1,x_2,y_2]$,表示第一个人在$(x_1,y_1)$,第二个人在$(x_2,y_2)$,朝着指定方向移动的合法字符串对数。

注意到,这样会统计重复,因为只向上,右,下,左走的字符串被重复计算了各一次,故容斥一下排除掉它们即可。

这样我们需要枚举$8\times8$种方向,但由于路径可逆的原因,实际上只进行了$\frac{8\times8}4=16$次Dp。
若忽略转移复杂度,时间复杂度为$O(16n^4)$。


代码

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>

using namespace std;

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {
if(x=='-')bj=-1;
x=getchar();
}
while(isdigit(x)) {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

const int maxn=35,mod=1e9+9;

struct pii {
int x,y;
pii(int x=0,int y=0):x(x),y(y) {}
};

int n,m,f[maxn][maxn][maxn][maxn],g[3][3][3][3],ans=0;
char map[maxn][maxn];
vector<pii> dxy1,dxy2;

void add(int &x,int v) {
x+=v;
if(x>=mod)x-=mod;
}

int Dp(int x1,int y1,int x2,int y2) {
if(x1<1||x1>n||y1<1||y1>m||x2<1||x2>n||y2<1||y2>m||map[x1][y1]!=map[x2][y2])return 0;
if(~f[x1][y1][x2][y2])return f[x1][y1][x2][y2];
f[x1][y1][x2][y2]=1;
for(pii d1:dxy1)for(pii d2:dxy2)add(f[x1][y1][x2][y2],Dp(x1+d1.x,y1+d1.y,x2+d2.x,y2+d2.y));
return f[x1][y1][x2][y2];
}

int Solve(int dx1,int dy1,int dx2,int dy2) {
if(~g[dx1+1][dy1+1][dx2+1][dy2+1])return g[dx1+1][dy1+1][dx2+1][dy2+1];
dxy1.clear(),dxy2.clear();
for(int i=-1; i<=1; i++) {
if(i&&i!=dx1)continue;
for(int j=-1; j<=1; j++) {
if((!i&&!j)||(j&&j!=dy1))continue;
dxy1.push_back(pii(i,j));
}
}
for(int i=-1; i<=1; i++) {
if(i&&i!=dx2)continue;
for(int j=-1; j<=1; j++) {
if((!i&&!j)||(j&&j!=dy2))continue;
dxy2.push_back(pii(i,j));
}
}
memset(f,-1,sizeof(f));
int sum=0;
for(int sx1=1; sx1<=n; sx1++)
for(int sy1=1; sy1<=m; sy1++)
for(int sx2=1; sx2<=n; sx2++)
for(int sy2=1; sy2<=m; sy2++)
add(sum,Dp(sx1,sy1,sx2,sy2));
g[dx1+1][dy1+1][dx2+1][dy2+1]=g[dx2+1][dy2+1][dx1+1][dy1+1]=g[-dx1+1][-dy1+1][-dx2+1][-dy2+1]=g[-dx2+1][-dy2+1][-dx1+1][-dy1+1]=sum;
return sum;
}

int Solve(int x,int y) {
int sum=0;
add(sum,Solve(-1,-1,x,y));
add(sum,Solve(-1,1,x,y));
add(sum,Solve(1,-1,x,y));
add(sum,Solve(1,1,x,y));
add(sum,mod-Solve(-1,0,x,y));
add(sum,mod-Solve(1,0,x,y));
add(sum,mod-Solve(0,-1,x,y));
add(sum,mod-Solve(0,1,x,y));
return sum;
}

int main() {
n=Get_Int();
m=Get_Int();
for(int i=1; i<=n; i++)scanf("%s",map[i]+1);
memset(g,-1,sizeof(g));
add(ans,Solve(-1,-1));
add(ans,Solve(-1,1));
add(ans,Solve(1,-1));
add(ans,Solve(1,1));
add(ans,mod-Solve(-1,0));
add(ans,mod-Solve(1,0));
add(ans,mod-Solve(0,-1));
add(ans,mod-Solve(0,1));
printf("%d\n",ans);
return 0;
}
姥爷们赏瓶冰阔落吧~