题意
F.A.Qs | Home | Discuss | ProblemSet | Status | Ranklist | Contest | 入门OJ | ModifyUser autoint | Logout | 捐赠本站 |
---|
Problem 1494. -- [NOI2007]生成树计数
1494: [NOI2007]生成树计数
Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 1024 Solved: 592
[Submit][Status][Discuss]
Description
Input
包含两个整数k,n,由一个空格分隔。k表示要将所有距离不超过k(含k)的结点连接起来,n表示有n个结点。
Output
输出一个整数,表示生成树的个数。由于答案可能比较大,所以你 只要输出答案除65521 的余数即可。
Sample Input
Sample Output
HINT
Source
[Submit][Status][Discuss]
HOME
Back
中文
فارسی
English
ไทย
分析
参照xyz32768的题解。
定义状态: \(f[i][S]\)表示\(i\)个点的图,编号差\(≤k\)的点对之间有连边,现选出一些边,连通第\(1\)个点到第\(i−k\)个点,第\(i−k+1\)个点到第\(i\)个点的连通性为\(S\),第\(i−k+1\)个点到第\(i\)个点至少存在一点与前\(i−1\)个点连通,且选出的边无环的方案数。
注意这里的\(S\)压缩连通性使用的是最小表示法: 对连通块进行标号,从\(1\)到连通块个数,首次出现位置越靠前的连通块编号越小。
会发现有效\(S\)的个数是贝尔数,即第二类斯特林数的前缀和。 \(k=5\)时状态数只有\(52\) 。
如何求\(f[i+1][T]\)从\(f[i][S]\)的转移系数呢?
我们可以对于一个\(S\),\(2^k\)枚举第\(i−k+1\)个点到第\(i\)个点是否与\(i+1\)连边,大力计算即可。
但要注意:
- 如果第\(i−k+1\)个点在第\(i−k+1\)到第\(i\)个点中单独属于一个连通块,那么\(i−k+1\)和\(i+1\)间必须连边,否则不能保证「连通前\(i−k+1\)个点」。
- 不能由\(i\)连向第\(i−k+1\)个点到第\(i\)个点中的同一个连通块,否则会形成环。
发现转移系数不变且为一阶,因此直接上矩阵快速幂。
代码
参照Icefox_zhx的代码。dfs写有许多好处。
我们可以先用一个DFS预处理出所有可能出现的连通性的状态。然后再枚举连通性状态S以及下一个点和S里的K个点中的哪些点连边,再判断从连通性状态S转移出来的新状态S′是否是合法的,若合法,在邻接矩阵里,标记从S到S′的方案数加1.
#include<bits/stdc++.h>
#define rg register
#define il inline
#define co const
template<class T>il T read(){
rg T data=0,w=1;rg char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') w=-1;ch=getchar();}
while(isdigit(ch)) data=data*10+ch-'0',ch=getchar();
return data*w;
}
template<class T>il T read(rg T&x) {return x=read<T>();}
typedef long long ll;
using namespace std;
co int M=7,N=60,mod=65521;
int m;ll n;
int temp[M],sta[N][M],tot,ini[N];
void init_sta(int id){ //预处理所有状态的初始种类数
static int cnt[M];
memset(cnt,0,sizeof cnt);
for(int i=1;i<=m;++i) ++cnt[sta[id][i]];
ini[id]=1;
for(int i=1;cnt[i];++i)if(cnt[i]>2) ini[id]*=pow(cnt[i],cnt[i]-2);
//n个点的完全图的生成树个数为n^(n-2)个
}
void dfs_sta(int i,int x){ //前i-1个点分成了x个连通块
if(i==m+1) return memcpy(sta[++tot],temp,sizeof temp),init_sta(tot);
for(int j=1;j<=x+1;++j) temp[i]=j,dfs_sta(i+1,max(j,x));
}
struct matrix{
int a[N][N];
il int*operator[](int x){return a[x];}
il co int*operator[](int x)co{return a[x];}
matrix operator*(co matrix&b)co{
matrix c;
memset(c.a,0,sizeof c.a);
for(int i=1;i<=tot;++i)
for(int j=1;j<=tot;++j)
for(int k=1;k<=tot;++k)
c[i][j]=(c[i][j]+(ll)a[i][k]*b[k][j])%mod;
return c;
}
matrix operator^(ll k){
matrix x=*this,re;
memset(re.a,0,sizeof re.a);
for(int i=1;i<=tot;++i) re[i][i]=1;
for(;k;k>>=1,x=x*x)
if(k&1) re=re*x;
return re;
}
}trans;
bool f[M],edge[M]; //f[i]:i连通块是否已连过,edge[i]:i位置是否连边了
bool issame(int a[],int b[]){
for(int i=1;i<=m;++i)
if(a[i]!=b[i]) return 0;
return 1;
}
void get_tra(int id){ //求sta[id]此时转移到的状态a
static int a[M];
memcpy(a,sta[id],sizeof a);
for(int i=1;i<=m;++i)if(edge[i]){
if(a[m+1]==0) a[m+1]=a[i];
else for(int x=a[i],j=1;j<=m;++j)if(a[j]==x) a[j]=a[m+1];
}
for(int i=1;i<=m;++i) a[i]=a[i+1]; //把状态往前挪一个
static int num[M],cnt;
memset(num,0,sizeof num),cnt=0;
for(int i=1;i<=m;++i){ //重新标号,使得满足最小表示法
if(!num[a[i]]) num[a[i]]=++cnt;
a[i]=num[a[i]];
}
for(int i=1;i<=tot;++i)if(issame(a,sta[i]))
return ++trans[id][i],void();
}
void dfs_tra(int id,int i){
if(i==m+1) return get_tra(id);
dfs_tra(id,i+1);
if(!f[sta[id][i]]){
f[sta[id][i]]=1,edge[i]=1;
dfs_tra(id,i+1);
f[sta[id][i]]=0,edge[i]=0;
}
}
int main(){
// freopen(".in","r",stdin),freopen(".out","w",stdout);
read(m),read(n);
dfs_sta(1,0); //预处理出k个点的所有连接状态,用最小表示法表示,以及每种状态的初始种类数
for(int i=1;i<=tot;++i){
memset(f,0,sizeof f);
memset(edge,0,sizeof edge);
bool flag=1;
for(int j=2;j<=m;++j)
if(sta[i][j]==1) {flag=0;break;}
if(flag) f[1]=1,edge[1]=1,dfs_tra(i,2); //1必须连这个了。
else dfs_tra(i,1);
}
trans=trans^(n-m);
int ans=0;
for(int i=1;i<=tot;++i) ans=(ans+(ll)trans[i][1]*ini[i])%mod;
printf("%d\n",ans);
return 0;
}