題解：
這種數據范圍果斷矩陣乘法，其實dp什么的也特別顯然，就是求轉移矩陣特別惡心。
用 最小表示法（表示現學的壓力比較大） 表示連通性。
能多暴力就多暴力的枚舉，反正數據范圍小~
唯一需要注意的是轉移的時候有兩種情況是不合法的：
1、第(i-k)個點不和第(i-k+1)到i個點連通
2、第i個點連到已經在一個連通塊中的兩個點
?
wa了半天，然后不想做了的時候突然發現ac了。。莫名其妙。。。
?
代碼比較丑陋。。
View Code
1
#include <iostream>
2
#include <cstdlib>
3
#include <cstdio>
4
#include <cstring>
5
#include <algorithm>
6
7
#define
N 10
8
#define
SIZE 60
9
#define
mod 65521
10
11
using
namespace
std;
12
13
struct
MT
14
{
15
int
x,y;
16
long
long
mt[SIZE][SIZE];
17
}ans,zy;
18
19
int
hash[
100010
],antihash[
100010
];
20
int
m,fa[N],col[N],cnt;
21
long
long
n;
22
bool
map[N][N],vis[N][N];
23
24
inline MT
operator
*
(MT a,MT b)
25
{
26
MT c; memset(c.mt,
0
,
sizeof
c.mt);
27
c.x=a.x; c.y=
b.y;
28
for
(
int
i=
1
;i<=c.x;i++
)
29
for
(
int
j=
1
;j<=c.y;j++
)
30
for
(
int
k=
1
;k<=a.y;k++
)
31
c.mt[i][j]=(c.mt[i][j]+a.mt[i][k]*b.mt[k][j])%
mod;
32
return
c;
33
}
34
35
inline
int
findfa(
int
x)
36
{
37
if
(fa[x]!=x)
return
fa[x]=
findfa(fa[x]);
38
return
fa[x];
39
}
40
41
inline
void
check()
42
{
43
memset(vis,
1
,
sizeof
vis);
44
for
(
int
i=
1
;i<=m;i++) fa[i]=
i;
45
for
(
int
i=
1
;i<m;i++
)
46
for
(
int
j=
1
;j+i<=m;j++
)
47
if
(map[i][j])
48
{
49
if
(findfa(i)==findfa(i+j))
return
;
//
判環
50
else
fa[findfa(i)]=findfa(i+
j);
51
}
52
for
(
int
i=
1
;i<m;i++
)
53
for
(
int
j=
1
;j+i<=m;j++
)
54
vis[i][i+j]=vis[i+j][i]=!
map[i][j];
55
for
(
int
k=
1
;k<=m;k++)
//
傳遞閉包
56
for
(
int
i=
1
;i<=m;i++
)
57
for
(
int
j=
1
;j<=m;j++
)
58
{
59
if
(vis[i][j]==
0
)
continue
;
60
if
(vis[i][k]||vis[k][j])
continue
;
61
vis[i][j]=
0
;
62
}
63
int
tmp=
0
;
64
memset(col,-
1
,
sizeof
col);
65
for
(
int
i=
1
;i<=m;i++)
//
最小表示法
66
{
67
for
(
int
j=
1
;j<i;j++
)
68
if
(vis[j][i]==
0
) {col[i]=col[j];
break
;}
69
if
(col[i]==-
1
) col[i]=tmp++
;
70
}
71
tmp=
0
;
72
for
(
int
i=
1
;i<=m;i++) tmp=tmp*
10
+
col[i];
73
if
(hash[tmp]==
0
)
74
{
75
hash[tmp]=++cnt;
//
cnt個最小表示法
76
antihash[cnt]=
tmp;
77
}
78
ans.mt[hash[tmp]][
1
]++;
//
最小表示法代表的方案數
79
}
80
81
inline
void
dfs(
int
x,
int
y)
82
{
83
if
(x==m-
1
&&y==
2
) check();
84
else
if
(x+y==m+
1
) dfs(x+
1
,
1
);
85
else
86
{
87
map[x][y]=
1
; dfs(x,y+
1
);
88
map[x][y]=
0
; dfs(x,y+
1
);
89
}
90
}
91
92
inline
bool
uni()
93
{
94
for
(
int
i=
2
;i<=m;i++
)
95
if
(col[
1
]==col[i])
return
0
;
96
return
1
;
97
}
98
99
inline
int
trans(
int
zt)
100
{
101
memset(vis,
1
,
sizeof
vis);
102
for
(
int
i=
1
;i<=m;i++
)
103
for
(
int
j=i+
1
;j<=m;j++
)
104
if
(col[i]==col[j]) vis[i][j]=vis[j][i]=
0
;
105
for
(
int
i=
1
;i<=m;i++
)
106
if
(zt&(
1
<<(m-i))) vis[i][m+
1
]=vis[m+
1
][i]=
0
;
107
for
(
int
k=
1
;k<=m+
1
;k++)
//
傳遞閉包
108
for
(
int
i=
1
;i<=m+
1
;i++
)
109
for
(
int
j=
1
;j<=m+
1
;j++
)
110
{
111
if
(vis[i][j]==
0
)
continue
;
112
if
(vis[i][k]||vis[k][j])
continue
;
113
vis[i][j]=
0
;
114
}
115
memset(col,-
1
,
sizeof
col);
116
int
tmp=
0
;
117
for
(
int
i=
2
;i<=m+
1
;i++)
//
最小表示法
118
{
119
for
(
int
j=
2
;j<i;j++
)
120
if
(vis[j][i]==
0
) {col[i]=col[j];
break
;}
121
if
(col[i]==-
1
) col[i]=tmp++
;
122
}
123
tmp=
0
;
124
for
(
int
i=
2
;i<=m+
1
;i++) tmp=tmp*
10
+
col[i];
125
return
tmp;
126
}
127
128
inline
int
solve(
int
c,
int
zt)
129
{
130
for
(
int
i=m;i>=
1
;i--
)
131
{
132
col[i]=c%
10
;
133
c/=
10
;
134
}
135
col[m+
1
]=-
1
;
136
for
(
int
i=
1
;i<=m;i++
)
137
for
(
int
j=i+
1
;j<=m;j++
)
138
if
(col[i]==col[j]&&(zt&(
1
<<(m-i)))&&(zt&(
1
<<(m-j))))
return
-
1
;
//
環
139
if
(!(zt&(
1
<<(m-
1
)))&&uni())
return
-
1
;
//
最左側的點不連通
140
return
trans(zt);
141
}
142
143
inline
void
get_det()
//
求出轉移矩陣
144
{
145
ans.x=cnt; ans.y=
1
;
146
zy.x=zy.y=
cnt;
147
for
(
int
i=
1
;i<=cnt;i++
)
148
{
149
int
lim=
1
<<
m,pa;
150
for
(
int
j=
0
;j<lim;j++
)
151
{
152
pa=
solve(antihash[i],j);
153
if
(pa==-
1
)
continue
;
154
zy.mt[hash[pa]][i]++
;
155
}
156
}
157
}
158
159
inline
void
go()
160
{
161
scanf(
"
%d%lld
"
,&m,&
n);
162
if
(m==
1
) {puts(
"
1
"
);
return
;}
163
dfs(
1
,
1
);
164
get_det();
165
n-=(
long
long
)m;
166
while
(n)
167
{
168
if
(n&(1LL)) ans=zy*
ans;
169
zy=zy*
zy;
170
n>>=
1LL;
171
}
172
printf(
"
%lld\n
"
,ans.mt[hash[
0
]][
1
]);
173
}
174
175
int
main()
176
{
177
go();
178
return
0
;
179
}
?
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
