【洛谷】题解 P2109 【[NOI2007]生成树计数】

双倍经验吼啊！！

原题

思路：

首先，我们来确定前k个点的状态。

原本想用一个k位二进制数记录每个点跟它前面的k个点的连接情况，

但是这样处理不了一个问题，就是如何排除环的存在。

所以借鉴了一些解题报告，发现可以在由1~n依次处理节点时，

用一个k位k进制数来记录最近k个点所在的联通块的情况，

这样的状态其实并不多，n=5的时候有52个。

为了避免状态的冗余，就要保证一个状态只有一种表示形式，

为此我学习了非常巧妙的“最小表示法”(SOJ 3296)。

但其实本题与最小表示法并无关系，

最小表示法求的是一个串的字典序最小的循环表示。

而本题中显然不能对状态进行循环表示，

而只能在已知哪几个节点处于同一个联通块的情况下，改变联通块的标号，使得得到的状态最小。

当我们枚举出了初始的状态后，例如节点1,2,3属于联通块0，节点4,5属于联通块1。

那么，同一个联通块中，生成树的形态仍然有很多。

在后面的状态转移的过程中，我们可以通过枚举边来自然的进行转移。

但是初始状态却没办法这样，对于一个初始状态，我们无法得知有多少种连边方式可以得到它。

本题给出了一个利用矩阵计算生成树个数(HDOJ 4305)的方法，具体可以参考周冬的《生成树的计数及其应用》：

对于有n个点的图，构造一个矩阵，使得：

若i==j，a[i][j]=dex[i]。（dex[i]为节点i的度数）。

否则，若点i和点j间有边相连，a[i][j]=-1。

若无边相连，a[i][j]=0。

然后求这个矩阵的行列式，得到的即是这个图的生成树个数。

当然，如果计算的行列式的值非常大，自然就要对某个数取模（本题中K<=5，没有这个必要）。

对于行列式模任意值的解法，bjin的论文《欧几里得算法的应用》中有介绍。

另外，个人觉得bjin的两道题： SPOJ DETER3（行列式模） 和 SPOJ MSTS（最小生成树计数，HDOJ 4408与此题类似），

非常适合作为本题的后续练习。

显然，对于这道题。

假设相邻K个点中，有x个点同属于1号联通块

那么这x个点中两两间都必然是可以连边的。

我们要求的是x个点的完全图的生成树种数，

得到的即是联通块1在当前的K个点这个部分，所能得到的生成树种数。

当然，其实不必真的去计算行列式，题目的开头已经告诉我们了，n个节点的完全图的生成树个数是n^(n-2)。

这个结论可以用cayley定理来证明。

处理了初始状态之后，再来看一下状态的转移。

从序号由小到大处理各节点。

每处理一个节点x时，用一个k位二进制数枚举这个点跟它前面的k个点的连接情况，

然后就可以由[x-k-1,x-1]的原状态转化到[x-k,x]的新状态。

当然，这过程中可能出现环，这个可以用并查集来判断，如果出现环，这个转移就是无效的。

显然，按节点顺序从小到大处理，每次在标记一个新的联通块的时候，使用当前未使用的最小标号即可。

我们不难看出，状态转移时的倍数关系，只与原状态和新状态有关，跟点的序号无关。

因此我们可以构造一个初始向量和一个转移矩阵。

我构造的初始向量g[]是一个行向量。每个位置代表一种初始状态。

每个位置的值，就是前k个点有多少种连接方式能够达成这种状态。

然后对于状态转移矩阵f[][]，第i行第j列表示由状态i转移到状态j有多少种合法的连接方式（不成环且第x-k个点至少与x-k+1~x中的一个点同一个联通块）。

求出g*pow(f,n-k)之后，对于得到的行向量中每个位置的数值，就代表了有多少种达到这个状态的方法。

然而，这些状态并不都是有用的。

只有所有点处于同一个联通快的那个状态是有用的，也就是状态0。

所以输出g[0][0]即可。

PS：

做这道题的过程中主要参考了俞华程的论文《矩阵乘法在信息学中的应用》和陈丹琦的论文《基于连通性状态压缩的动态规划问题》（恰好以上两位也是OI界有名的赛场伉俪，有木有有木有！），以及ACMonster和whjpji的解题报告。

非常感谢！

还要谢谢适牛借给我他超级长长长长长长长长长长的矩阵类模板哟~~~~~~~~

代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
const int Mx=200;
const int p=65521;
using namespace std;
ll n;
int K,tot/*状态总数*/,Tr_siz[]={1,1,1,3,16,125}/*完全图的生成树个数*/;
int fa[Mx],siz[Mx]/*第i个联通块的大小*/,status[600],hash[1<<16]/*hash[S]=状态S的编号*/;

struct Matrix
{
    int n,m; ll num[Mx][Mx];
    Matrix() { n=m=0; memset(num,0,sizeof(num)); }
}A,trans;
Matrix operator*(Matrix a,Matrix b)
{
    Matrix c;
    c.n=a.n,c.m=b.m;
    for(int k=1;k<=a.m;k++)
        for(int i=1;i<=c.n;i++)
            for(int j=1;j<=c.m;j++)
                c.num[i][j]=(c.num[i][j]+a.num[i][k]*b.num[k][j]%p)%p;
    return c;
}
void Pow(ll c)
{
    while(c)
    {
        if(c&1) A=A*trans;
        trans=trans*trans;
        c>>=1;
    }
}

void dfs(int x,int sta) //当前要加入第x个点的联通状态，当前的状态为sta
{
    if(x==K+1)
    {
        memset(siz,0,sizeof(siz));
        A.num[1][++tot]=1;
        for(int i=1;i<=K;i++)
            siz[sta>>((i-1)*3)&7]++;
        for(int i=0;i<K;i++)
            A.num[1][tot]*=Tr_siz[siz[i]];
        status[tot]=sta;
        hash[sta]=tot;
        return;
    }
    int tmp=-1; //联通块的最大编号,联通块编号的区间是[0,K-1]
    for(int i=1;i<x;i++) //!!!当前的sta里只保存了1~pos-1这些点的连通性
        tmp=max(tmp,sta>>((i-1)*3)&7);
    for(int i=0;i<=tmp+1&&i<K;i++)
        dfs(x+1,sta<<3|i);
}

int find(int x) 
{
    if(fa[x]==x) return x;
    return fa[x]=find(fa[x]);
}

int Get_Status() //用当前的并查集来求出新的点2到点k+1的最小表示
{
    int sta=0,tot=0;
    bool vis[Mx]; memset(vis,false,sizeof(vis));
    for(int i=K+1;i>=2;i--)
        if(!vis[i])
        {
            vis[i]=true,sta|=tot<<((i-2)*3);
            for(int j=i-1;j>=2;j--)
                if(find(i)==find(j))
                    vis[j]=true,sta|=tot<<((j-2)*3);
            tot++;
        }
    return hash[sta];
}

void cal(int sta,int addsta) //用加边状态addsta去更新最小表示法sta,addsta里的第i位为1表示第k+1个点要和点i+1连新边
{
    for(int i=0;i<=K+1;i++) fa[i]=i;
    for(int i=1;i<=K;i++) //枚举点对(i,j)是否在最小表示法里的同一联通块内，将最小表示法中的连通性用并查集表示
        for(int j=i+1;j<=K;j++)
            if((status[sta]>>((i-1)*3)&7)==(status[sta]>>((j-1)*3)&7))
            {
                int rooti=find(i),rootj=find(j);
                if(rooti!=rootj) fa[rooti]=rootj;
            }
    for(int i=1;i<=K;i++)
        if(addsta&(1<<(i-1)))
        {
            int rooti=find(i),rootj=find(K+1);
            if(rooti==rootj) return; //判环，加的新边的两端点原来就是联通的，加入新边后会出现环
            fa[rooti]=rootj;
        }
    bool flag=false; //flag=true表示有点和点1联通
    for(int i=2;i<=K+1;i++)
        if(find(i)==find(1))
        {
            flag=true; break;
        }
    if(!flag) return; //点1不链接后面的点，那么这个生成树不联通
    trans.num[sta][Get_Status()]++;
}

int main()
{
    scanf("%d%lld",&K,&n);
    dfs(1,0); A.n=1; A.m=trans.n=trans.m=tot;
    for(int i=1;i<=tot;i++)
        for(int j=0;j<(1<<K);j++) cal(i,j);
    Pow(n-K); printf("%lld\n",A.num[1][1]);
    return 0;
}