BZOJ1494:[NOI2007]生成树计数 矩阵乘法+最小表示法+插头dp

思路:

从前向后考虑每一个点,不难发现每个点只能向它的前\(k\)个点连边.

因此我们维护一下最后\(k\)个点的连通性,然后做状压dp.

我们用最小表示法来表示\(k\)个点的连通性,比如12123这种形式,相同的数字表示在相同集合中.

然后我们就枚举一下第\(k+1\)个点如何向前\(k\)个点连边.

注意:合法的连边不能出现环,同时还要保证第\(1\)个点不能被孤立.

然后就有了一个转移矩阵,就可以跑矩乘了.

注意每个状态的初始方案并不是一,而是每个每个连通图的所有生成树的方案之积.

而由Prufer序列可得\(n\)个点的生成树总数为\(n^{n-2}\).

至此应该没有什么问题了(除了代码实现).

#include<map>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;
 
long long n;int k;
 
int lim;
 
int cnt,seq[110][10],now[10],vis[10];
 
void dfs(int dep){
    if(dep==k+1){
        memset(vis,0,sizeof vis);
        for(int i=1;i<=k;++i)if(!vis[now[i]])vis[now[i]]=i;
        for(int i=1;i<=lim;++i)if(!vis[i])return;
        for(int i=1;i<=lim;++i)for(int j=i+1;j<=lim;++j)if(vis[i]>vis[j])return;
         
        ++cnt;for(int i=1;i<=k;++i)seq[cnt][i]=now[i];
        return;
    }
     
    for(int i=1;i<=lim;++i)now[dep]=i,dfs(dep+1);
}
 
#define Min(x,y) ((x)<(y)?(x):(x))
 
inline int calc(int d){
    int mi=1,re=0;
    for(int i=1;i<=k;++i)re+=mi*seq[d][i],mi*=10;
    return re;
}
map<int,int>M;
 
static const int mod=65521;
inline void inc(int&x,int y){if((x+=y)>=mod)x-=mod;}
 
struct Matrix{
    int w,h,d[110][110];
    Matrix(int _w,int _h):w(_w),h(_h){memset(d,0,sizeof d);}
     
    inline void operator*=(const Matrix&B){
        Matrix C(w,B.h);
        for(int i=1;i<=C.w;++i)for(int j=1;j<=C.h;++j)
            for(int k=1;k<=h;++k)inc(C.d[i][j],(long long)d[i][k]*B.d[k][j]%mod);
        *this=C;
    }
};
 
int pre[10],pa[10],nowseq[10];
 
inline int find(int p[],int x){return x==p[x]?x:p[x]=find(p,p[x]);}
inline void merge(int p[],int x,int y){p[find(p,x)]=find(p,y);}
 
const int get[]={1,1,1,3,16,125};
 
int main(){
    scanf("%d%lld",&k,&n),k=Min(k,n-1);register int i,j;
     
    for(i=1;i<=k;++i){
        lim=i,dfs(1);
    }
     
    Matrix ans(1,cnt);
    for(i=1;i<=cnt;++i){
        ans.d[1][i]=1;
        for(j=1;j<=k;++j){int count=0;for(int q=1;q<=k;++q)if(seq[i][q]==j)++count;ans.d[1][i]*=get[count];}
         
        M[calc(i)]=i;
    }
     
    Matrix add(cnt,cnt);
     
    for(int t=1;t<=cnt;++t){
        for(i=1;i<=k+1;++i)pre[i]=i;
        for(i=1;i<=k;++i)for(j=i+1;j<=k;++j)if(seq[t][i]==seq[t][j])merge(pre,i,j);
         
        for(int S=0;S<(1<<k);++S){
            memcpy(pa,pre,sizeof pa);
            bool can=1;
            for(i=0;i<k;++i)if((S>>i)&1){if(find(pa,i+1)==find(pa,k+1))can=0;else merge(pa,i+1,k+1);}
            if(!can)continue;
             
            for(i=1;i<=k+1;++i)pa[i]=find(pa,i);
             
            memset(nowseq,0,sizeof nowseq);
            int id=0;
            for(i=1;i<=k+1;++i){
                if(nowseq[i]==0){
                    ++id;
                    for(j=i;j<=k+1;++j)if(pa[j]==pa[i])nowseq[j]=id;
                }
            }
             
            bool ok=0;
            for(i=2;i<=k+1;++i)if(nowseq[1]==nowseq[i]){ok=1;break;}
             
            if(ok){
                memset(nowseq,0,sizeof nowseq);
                id=0;
                for(i=2;i<=k+1;++i){
                    if(nowseq[i]==0){
                        ++id;
                        for(j=i;j<=k+1;++j)if(pa[j]==pa[i])nowseq[j]=id;
                    }
                }
                 
                int mi=1,re=0;
                for(i=2;i<=k+1;++i)re+=mi*nowseq[i],mi*=10;
                 
                if(M[re]==0)puts("WA");
                inc(add.d[t][M[re]],1);
            }
        }
    }
     
    n-=k;
    for(;n;n>>=1,add*=add)if(n&1)ans*=add;
     
    printf("%d",ans.d[1][1]);
     
    return 0;
}