「NOI2007」生成树计数 - 轮廓线Dp+矩阵快速幂 | Bill Yang's Blog

「NOI2007」生成树计数 - 轮廓线Dp+矩阵快速幂

题目大意

给一个有$n$个结点的图,每个点与其前$k$个点有边相连,统计该图的生成树个数。


数据分析

若直接使用提示的做法,时间复杂度$O(n!\times n)$,这样可以得到40分。
若使用高斯消元/LU分解的方法,时间复杂度$O(n^3)$,这样可以得到60分。
观察题目,我们发现$k$很小,那么矩阵中有很多元素为0,因此我们可以在高斯消元的时候对0值不作处理,这样时间复杂度是$O(n^2k)$,可以通过70分的数据。
本题能拿到70分已经很不错了。


观察第8组数据,$n$值不允许有平方的时间,而$k$允许有阶乘级的时间,故$O(nk!)$是可行的。
观察第9~10组数据,$n$非常大,只能采用log级别的方法,故应采用$O(\log_2(n)\times k!)$的时间复杂度。


初步想法

观察题目的图,我们发现其类似一个线性关系。
故我们可以采用动规的方法统计方案。
但是我们发现动规转移与图的连通关系有关,因此我们需要将连通关系表示出来。
可参考 2008年Day2论文集 陈丹琦《基于连通性状态压缩的动态规划问题》
该论文提出了一种基于最小表示法表示状态的轮廓线Dp,有下面两句极为有用的话:


  • 存在一个序,在这个序中有边相连的点的距离不超过k.
  • k一定是一个比较小的数,以这k个数为轮廓线确立状态.

根据题目我们可以以结点$1,2,3,\ldots,n$为顺序,以当前结点前$k$个点为轮廓线进行Dp。
因此我们可以使用最小表示法的状态压缩对这$k$个数作出处理。
设$f[i.S]$表示前$i$个点,区间$[i-k+1,i]$的连通性为S的生成树个数。
其中$S$用一个二进制数表示,根据最小表示法,我们使用相同的数字表示同一个连通块,故我们使用$0,1,2,\ldots,k-1$作为每个点的状态的数值。
$\because$最大的数值为$k-1=4$,而4的二进制表示$(4)_{10}=(100)_{2}$ 占3位。
又$\because$最多$k$个数。
$\therefore$最多占15位,即$2^{15}$。
$\therefore$可以使用二进制来表示$S$。

由于前k个结点比较特殊,不一定有k个前驱,故需要初始化Dp边界:

$num$是$S$中连通块数目
我们需要写一个转移函数判断$S’\rightarrow S$的转移是否兼容。
时间复杂度约$O(nt^2k^2)$,$t$为最小表示法合法状态数,由暴力程序得到$t\le52$,时间效率低,且编程复杂度较高,不易于实现。


考虑一个小优化,与其枚举两个状态判断兼容,不如枚举一个状态再枚举其转移情况。
具体的,我们先枚举出上一个状态$S’$,再枚举转移向量$A$,$A$表示新点$i$与哪些点相连,通过$S’,A$构造出当前状态$S$。
时间复杂度$O(nt2^kk^2)$,勉强可以卡过第8组数据。
具体的构造方法是:
通过上一个状态$S’$将相同数值的点用并查集连起来,然后用并查集将新点$i$与转移向量中值为1的点连起来,最后用并查集构造出新的最小表示法状态$S$。
注意在转移时判断成环,以及孤立$i-k$点,这些都是不合法的

什么是孤立$i-k$点?
即$i-k$点只可能与区间$[i-k+1,i]$中的点相连,若这些点都没有连向它的边,那么原生成树不连通,不合法。


算法优化

观察转移方程:

这个动规状态$f[i,S]$只与$f[i-1,S’]$有关且为线性关系。
且$t\le50,n$极大,故我们可以使用矩阵快速幂优化。
转移矩阵的构造与上述的状态转移类似,就不再赘述。


具体步骤

1.用一次Dfs预处理出所有可能出现的连通性的状态,并统计出初始向量$A$前k个结点的各种状态的方案数。
2.然后再枚举连通性状态$S’$以及下一个点和$S’$里的$k$个点中的哪些点连边,使用并查集构造出新状态$S$,同时判断是否合法。
3.若合法,在转移矩阵$B$中将$B[S’,S]+1$
4.计算出$C=A\times B^{n-k}$,$C[1,1]$即为答案。


代码

代码中有详细注释

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
141
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=55,mod=65521;
struct Matrix {
LL n,m,a[maxn][maxn];
Matrix() {}
Matrix(LL n,LL m) {
init(n,m);
}
Matrix(LL n,LL m,char E) { //单位矩阵
init(n,m);
for(int i=1; i<=n; i++)a[i][i]=1;
}
void init(LL n,LL m) {
this->n=n;
this->m=m;
memset(a,0,sizeof(a));
}
LL* operator [] (const LL x) {
return a[x];
}
Matrix operator * (Matrix b) {
Matrix c(n,b.m);
for(int i=1; i<=n; i++)
for(int j=1; j<=b.m; j++)
for(int k=1; k<=m; k++)
c[i][j]=(c[i][j]+a[i][k]*b[k][j]%mod)%mod;
return c;
}
void operator *= (Matrix& b) {
*this=*this*b;
}
Matrix operator ^ (LL b) {
Matrix ans(n,m,'e'),a=*this;
while(b>0) {
if(b&1)ans=ans*a;
a*=a;
b>>=1;
}
return ans;
}
};
LL n,tmp[55]; //tmp[]临时保存初始向量A的值
const int Full[]= {1,1,1,3,16,125};
int k,state[55],Hash[1<<16],num[15],tot=0;
#define State(status,i) (status>>((i-1)*3)&7) //状态status中第i个点的状态
void Dfs(int Now,int status) { //当前要加入Now点的状态,当前状态为status(二进制,每个点用三位保存,因为连通块最多:0/1/2/3/4,4的二进制有3位)
if(Now==k+1) {
memset(num,0,sizeof(num));
for(int i=1; i<=k; i++)num[State(status,i)]++; //统计当前轮廓线中编号为i的连通块的大小
tmp[++tot]=1;
for(int i=0; i<k; i++)tmp[tot]*=Full[num[i]]; //完全图生成树个数
state[tot]=status; //保存编号->状态
Hash[status]=tot; //保存状态->编号
return;
}
int Max=-1;
for(int i=1; i<Now; i++)Max=max(Max,State(status,i)); //统计当前连通块的最大编号,当前点就可以在[0,Max+1]中选择状态
for(int i=0; i<=min(Max+1,k); i++)Dfs(Now+1,status<<3|i);
}
int father[15];
int Get_Father(int x) {
if(father[x]==x)return x;
return father[x]=Get_Father(father[x]);
}
int Get_Status() { //用当前的并查集求出2~k+1的连通状态
bool vst[15]= {0};
int num[15]= {0},tot=-1; //num[]记录连通块编号(0/1/2/3/4)
for(int i=2; i<=k+1; i++) {
if(vst[i])continue;
num[i]=++tot;
for(int j=i+1; j<=k+1; j++)
if(Get_Father(i)==Get_Father(j)) {
num[j]=tot;
vst[j]=1;
}
}
int status=0;
for(int i=2; i<=k+1; i++)status=status<<3|num[i];
return Hash[status];
}
Matrix B;
void Cal(int status,int addstatus) { //用加边状态更新连通状态,addstatus中第i位表示新点k+1要和i+1点连边
for(int i=0; i<=k+1; i++)father[i]=i;
for(int i=1; i<=k; i++)
for(int j=i+1; j<=k; j++)
if(State(state[status],k-i+1)==State(state[status],k-j+1)) { //因为state状态是小的编号在高位 故此处应反过来
int fx=Get_Father(i),fy=Get_Father(j);
if(fx!=fy)father[fx]=fy;
}
for(int i=1; i<=k; i++)
if(addstatus&(1<<(i-1))) { //有边相连
int fx=Get_Father(k+1),fy=Get_Father(i);
if(fx==fy)return; //若已连通,加入此边会构成环,故不合法
father[fx]=fy;
}
bool bj=0;
for(int i=2; i<=k+1; i++)
if(Get_Father(i)==Get_Father(1)) {
bj=1;
break;
}
if(!bj)return; //点1没有连接后面的点,生成树不连通,不合法
B[status][Get_Status()]++; //转移矩阵的转移方案+1
}
int main() {
k=Get_Int();
n=Get_Int();
Dfs(1,0);
Matrix A(1,tot);
for(int i=1; i<=tot; i++)A[1][i]=tmp[i];
B.init(tot,tot);
for(int i=1; i<=tot; i++)
for(int j=0; j<(1<<k); j++) //加边状态
Cal(i,j);
A=A*(B^(n-k));
printf("%lld\n",A[1][1]);
return 0;
}

本篇文章有用吗?有用还不快点击!
0%