题目描述
最近,小栋在无向连通图的生成树个数计算方面有了惊人的进展,他发现:
个结点的环的生成树个数为
。
个结点的完全图的生成树个数为
。
这两个发现让小栋欣喜若狂,由此更加坚定了他继续计算生成树个数的想法,他要计算出各种各样图的生成树数目。
一天,小栋和同学聚会,大家围坐在一张大圆桌周围。小栋看了看,马上想到了生成树问题。如果把每个同学看成一个结点,邻座(结点间距离为1)的同学间连一条边,就变成了一个环。可是,小栋对环的计数已经十分娴熟且不再感兴趣。于是,小栋又把图变了一下:不仅把邻座的同学之间连一条边,还把相隔一个座位(结点间距离为2)的同学之间也连一条边,将结点间有边直接相连的这两种情况统称为有边相连,如图1所示。
小栋以前没有计算过这类图的生成树个数,但是,他想起了老师讲过的计算任意图的生成树个数的一种通用方法:构造一个的矩阵
,其中当
时,
;
时,
;其他情况
,其中di表示结点i的度数。
小栋发现利用通用方法,因计算过于复杂而很难算出来,而且用其他方法也难以找到更简便的公式进行计算。于是,他将图做了简化,从一个地方将圆桌断开,这样所有的同学形成了一条链,连接距离为1和距离为2的点。例如八个点的情形如下:
这样生成树的总数就减少了很多。小栋不停的思考,一直到聚会结束,终于找到了一种快捷的方法计算出这个图的生成树个数。可是,如果把距离为3的点也连起来,小栋就不知道如何快捷计算了。现在,请你帮助小栋计算这类图的生成树的数目。
输入格式
包含两个整数,由一个空格分隔。
表示要将所有距离不超过
的结点连接起来,
表示有
个结点。
输出格式
输出一个整数,表示生成树的个数。由于答案可能比较大,所以你 只要输出答案除65521的余数即可。
题目解析
这题似乎用题目介绍的行列式方法分数很多?然而距离正解似乎有点遥远啊。
注意到只有距离不超过的点有边相连。考虑一棵生成树,对于一个点
,在不考虑与
后面的点有关的边时,任意
的点一定互相连通,且至少存在某一
与
中的某点有边相连。所以我们在构造一棵生成树时,在点
处向前连边时只需要考虑
中点的连通性。
很小,所以我们将
中点的连通性用最小表示法表示。如
时,
表示三点连通;
表示后两点连通,但与第一个点不连通…… 经计算,可以发现在
时合法状态数也只有52种。
我们先暴力预处理所有状态和合法的转移。令为考虑到
,
的连通状态为
的方案数;
为状态
转移到状态
的方案数,则有
显然上述式子是可以用矩阵快速幂优化的。令状态数为,时间复杂度为
。
话说代码大部分篇幅都用在预处理转移矩阵和初始值矩阵上了,难道是姿势不对?
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 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 |
/************************************************************** Problem: 1494 User: frank_c1 Language: C++ Result: Accepted Time:400 ms Memory:1468 kb ****************************************************************/ #include <set> #include <map> #include <queue> #include <ctime> #include <cmath> #include <cstdio> #include <vector> #include <string> #include <cctype> #include <bitset> #include <cstring> #include <cstdlib> #include <utility> #include <iostream> #include <algorithm> #define REP(i,a,b) for(int i=(a);i<=(b);i++) #define PER(i,a,b) for(int i=(a);i>=(b);i--) #define RVC(i,S) for(int i=0;i<(S).size();i++) #define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next) using namespace std; typedef long long LL; typedef pair<int,int> pii; template<class T> inline void read(T& num) { bool start=false,neg=false; char c; num=0; while((c=getchar())!=EOF) { if(c=='-') start=neg=true; else if(c>='0' && c<='9') { start=true; num=num*10+c-'0'; } else if(start) break; } if(neg) num=-num; } /*============ Header Template ============*/ const int mo=65521; struct Matrix { int r,c; LL mat[60][60]; Matrix(int a=0,int b=0):r(a),c(b) { memset(mat,0,sizeof(mat)); } } G,A; Matrix operator * (Matrix a,Matrix b) { Matrix c(a.r,b.c); REP(k,1,a.c) REP(i,1,a.r) REP(j,1,b.c) c.mat[i][j]=(c.mat[i][j]+a.mat[i][k]*b.mat[k][j])%mo; return c; } Matrix MatPow(Matrix a,LL p) { Matrix c(a.r,a.c); REP(i,1,a.r) REP(j,1,a.c) c.mat[i][j]=(i==j); for(;p;p>>=1) { if(p&1) c=c*a; a=a*a; } return c; } const int maxn=301; int key[maxn],val[maxn]; int st[maxn],lst[maxn]; int fa[maxn],vis[maxn]; int nval[maxn],lval[maxn]; int idx=0,tot=0,cnt=0; inline int hash(int x) { int p=x%mo; while(key[p]!=x && key[p]!=-1) { p++;if(p>=maxn) p-=maxn; } if(key[p]==-1) { ++idx;st[idx]=x;key[p]=x;val[p]=idx; } return val[p]; } int Find(int x) {return fa[x]==x?x:fa[x]=Find(fa[x]);} void init(int mx) { lval[1]=1;lst[cnt=1]=0; for(int n=1;n<mx;n++) { memset(st,0,sizeof(st)); memset(nval,0,sizeof(nval)); memset(key,-1,sizeof(key));idx=0; REP(i,1,cnt) { for(int c=0;c<(1<<n);c++) { int v=lst[i]; PER(k,n,1) vis[k]=0,fa[k]=v%mx+1,v/=mx; REP(k,1,n) { if(!vis[fa[k]]) vis[fa[k]]=k; fa[k]=vis[fa[k]]; } int f=1;fa[n+1]=n+1; REP(k,1,n) if(c&(1<<(k-1))) { int x=Find(k),y=Find(n+1); if(x==y) { f=0;break; } fa[x]=y; } if(!f) continue;f=0; tot=0; memset(vis,0,sizeof(vis)); REP(k,1,n+1) { int x=Find(k); if(!vis[x]) vis[x]=++tot; f=f*mx+vis[x]-1; } nval[hash(f)]+=lval[i]; } } cnt=idx; REP(i,1,idx) { lval[i]=nval[i];lst[i]=st[i]; } } G.r=G.c=A.r=idx;A.c=1; REP(i,1,idx) A.mat[i][1]=lval[i]; REP(i,1,idx) { for(int c=0;c<(1<<mx);c++) { int v=st[i]; PER(k,mx,1) vis[k]=0,fa[k]=v%mx+1,v/=mx; REP(k,1,mx) { if(!vis[fa[k]]) vis[fa[k]]=k; fa[k]=vis[fa[k]]; } int f=1;fa[mx+1]=mx+1; REP(k,1,mx) if(c&(1<<(k-1))) { int x=Find(k),y=Find(mx+1); if(x==y) {f=0;break;} fa[x]=y; } if(!f) continue;f=0; tot=0; memset(vis,0,sizeof(vis)); REP(k,2,mx+1) { int x=Find(k); if(!vis[x]) vis[x]=++tot; f=f*mx+vis[x]-1; } if(!vis[Find(1)]) continue; G.mat[hash(f)][i]++; } } } int B[maxn]; int main() { LL n;int k; read(k);read(n); init(k); A=MatPow(G,n-k)*A; printf("%lld\n",A.mat[hash(0)][1]); return 0; } |