[CF] 336E Vasily the Bear and Painting Square

发表于   |   分类于   |  

题意

　　最近老师考到了这道题,这里写一下这道题比较麻烦的思路

当$n=0$时有如下图像

当$n=1$时有如下图像

当$n=2$时有如下图像

题目要求对定的$n$的图像,染k个三角形(并不要求染最小的三角形),求染色方案数.
需要注意的是:即使染色完毕后结果图案相同,若某一步染的三角形不相同也算是不同的两种方案.

传送门

分析

可以发现染色是可以分层次的.
我们把$n$的图像分为$n$层,最内层为$0$,则可以一层一层向外染色.
如果想对小三角形染色,是与上一层及以内是否染过色无关的.
如果想对大三角形染色,我们只需要判断上一层及以内的一个染色方案中,某一象限内是否染过色即可.
我们画出图来分析

我们发现在划分为$n$层后层与层之间分为两层更加合适.
上图中从第$i$层到第$i+0.5$层的转移很简单,并不需要判断前$i$层之内某一象限是否被染过色(只有①,②,③,④可选)
重点是第$i+0.5$层到第$i+1$层
在这一层中我们可以选择

  1. 像⑥,⑦,⑧这样的小三角形
  2. 像⑤⑥,⑦⑧这样两个三角形拼接起来的中等大小的三角形
  3. 像第一象限和第二象限拼在一起的超级大三角形

于是按照这个思路我们可以求得层与层之间的转移
在从$i=0$开始循环一边,用已经求得的转移来转移,就可以求到大小为$n$的图,染$k$个三角形的方案数.

那么,题目说若某一步染的三角形不相同也算是不同,其实答案乘以$k!$就好了么.

好吧说这么多实现起来还是照样复杂…几乎都是抄的代码了 23333333

stO zhonghaoxi

代码

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
#include <cstdio>
#define Rep(i,l,r) for(i=(l);i<=(r);i++)
#define Rev(i,r,l) for(i=(r);i>=(l);i--)
int CH , NEG ;
template <typename TP>
inline void read(TP& ret) {
    ret = NEG = 0 ; while (CH=getchar() , CH<'!') ;
    if (CH == '-') NEG = true , CH = getchar() ;
    while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ;
    if (NEG) ret = -ret ;
}
template <typename TP>
inline void reads(TP& ret) {
truewhile (ret=getchar() , ret<'!') ;
truewhile (CH=getchar() , CH>'!') ;
}

#include <cstring>

const int  ansmod  = 1000000007 ;
#define  inc(a,b) {a+=b;if(a>=ansmod)a-=ansmod;}
#define  maxn  210LL//n
#define  maxk  210LL//k
#define  maxs  16LL//四位01状态
#define  maxq  5LL//四个象限
#define  maxt  10LL//一次转移最多增加8个三角形

int N , K ;
int g[16][10][16] = {0} ;
int h[5][10][2][2][16] = {0} ;
int f[401][210][16] = {0} ;
int num[16] ;

//我们把第i层到第i+1层拆为两个步骤
//即从第i层转移到第i+0.5层(立放到平放)和第i+0.5层到i+1层(平放到立放)
//g[原始状态][增加几个三角形][到达目标状态]的方案数
//h[前i个象限][增加了几个三角形][第i*2个三角形是否使用][第1个三角形是否使用][此时的状态]
//(第i*2个也就是前i个象限中的最后一个三角形)
//h是用来求g的
//求得g后可以用来求f
//最后要乘k的阶乘,因为染色方案结果相同,顺序不同也算不同

int i , j , k , A , B , use , last , first , now1 , now2 , cnt , can , Time , ans ;
int col[4] = {0} ;

int main() {
//	#define READ
true#ifdef  READ
truetruefreopen(".in" ,"r",stdin ) ;
truetruefreopen(".out","w",stdout) ;
true#endif
trueRep (A,0,16-1) {
truetruenum[B=A] = 0 ;
truetruewhile (B) num[A]+=(B&1) , B>>=1 ;
true}
trueRep (A,0,16-1) {
truetruememset(h , 0 , sizeof h) ;
truetrueh[1][0][0][0][A]=h[1][1][1][0][A|1]=h[1][2][1][1][A|1]=h[1][1][0][1][A|1]=1;
truetrueif (!(A&1)) h[1][1][1][1][A|1]=1;
truetrueRep (i,1,3) Rep (use,0,8) Rep (last,0,1) Rep (first,0,1)
truetruetrueRep (B,0,16-1) if (h[i][use][last][first][B])
truetruetruetrueRep (now1,0,1) Rep (now2,0,1) {
truetruetruetruetrueif (!now1 && !now2 && !((B>>i)&1))//当前这个象限不使用三角形且这个象限本来就是空的
truetruetruetruetruetrueinc(h[i+1][use+1][1][first][B|(1<<i)],h[i][use][last][first][B]);//那就添上一个大三角形
truetruetruetruetrueinc(h[i+1][use+now1+now2][now2][first][B|((now1|now2)<<i)],h[i][use][last][first][B]) ;
truetruetruetruetrueif (!last && !now1)
truetruetruetruetruetrueinc(h[i+1][use+1+now2][now2][first][B|(1<<i)|(1<<(i-1))],h[i][use][last][first][B]);
truetruetruetruetruetrue//与上一个象限的三角形拼接成一个三角形添入
truetruetruetruetrueif (!now1 && !now2 && !((B>>i)&1) && !((B>>(i-1))&1))
truetruetruetruetruetrueinc(h[i+1][use+1][1][first|(i==1)][B|(1<<i)|(1<<(i-1))],h[i][use][last][first][B]);
truetruetruetruetruetrue//如果两个相邻的象限都是空的,可以填一个很大的三角形 = =
truetruetruetrue}
truetrueRep (use,0,8) Rep (B,0,16-1)
truetruetrueinc(h[4][use+1][1][1][B|9],h[4][use][0][0][B]) ;
truetrueRep (use,0,8) Rep (B,0,16-1) if (!(B&1)&&!(B&8))
truetruetrueinc(h[4][use+1][1][1][B|9],h[4][use][0][0][B]) ;
truetrueRep (use,0,8) Rep (last,0,1) Rep (first,0,1) Rep (B,0,16-1)
truetruetrueinc(g[A][use][B],h[4][use][last][first][B]) ;
true}
trueRep (A,0,16-1) Rep(B,0,16-1) {
truetruecol[0]=col[1]=col[2]=col[3]=0;
truetruecnt = 0 ;
truetrueRep (i , 0 , 4-1)
truetruetruecol[i] = ((A>>i)&1) , cnt += col[i] ;
truetruecan = true ;
truetrueRep (i,0,4-1) if ((B>>i)&1) {
truetruetrueif (col[i] || col[(i+1)%4]) can = false ;
truetruetruecol[i] = col[(i+1)%4] = true ;
truetruetruecnt ++ ;
truetrue}
truetrueif (!can) continue ;
truetrueK = 0 ;
truetrueRev (i,4-1,0)
truetruetrueK = (K<<1)|col[i] ;
truetruef[0][cnt][K] ++ ;
true}
trueRep (i,0,400-1) Rep (j,0,200) Rep (A,0,16-1)
truetrueif (f[i][j][A])
truetruetrueif (i&1) {
truetruetruetrue//从奇数转移到偶数,统计的形状是立起来的正方形
truetruetruetrueRep (k,0,8)
truetruetruetruetrue//所以这里最多有八个小三角形
truetruetruetruetrue//但在转移时应该包括了两个三角形拼起来的情况
truetruetruetruetruetrueRep (B,0,16-1)
truetruetruetruetruetruetrueinc(f[i+1][j+k][B],(long long)f[i][j][A]*g[A][k][B]%ansmod) ;
truetruetrue} else {
truetruetruetrue//从偶数转移到奇数,统计的形状是平方的正方形
truetruetruetrueRep (k,0,16-1)
truetruetruetruetrue//所以只用判断四个角是否有三角形即可
truetruetruetruetrueinc(f[i+1][j+num[k]][A|k],f[i][j][A]) ;
truetruetrue}
trueread(Time) ;
truewhile (Time --> 0) {
truetrueread(N) , read(K) ;
truetrueint ans = 0 ;
truetrueRep (A,0,16-1)
truetruetrueinc(ans,f[2*N][K][A]) ;
truetrueRep (i,1,K)
truetruetrueans = (long long)ans*i%ansmod ;
truetrueprintf("%d\n", ans) ;
true}
true#ifdef  READ
truetruefclose(stdin) ; fclose(stdout) ;
true#else
truetruegetchar() ; getchar() ;
true#endif
truereturn 0 ;
}

热评文章