题意：http://www.lydsy.com/JudgeOnline/problem.php?id=1494
sol ：前排膜拜http://blog.csdn.net/qpswwww/article/details/45362639
虽然dalao们说了一些最小表示法啊什么k=5时只有52种状态啊balabala，然而我并不会.......
因为k很小，可以考虑用状压来记录联通块信息，考虑dp
dp[i][j]表示前i个点，最后k个点联通情况为j时的方案数
由于n很大，考虑采用矩阵快速幂优化，用并查集判环&维护
那么最终可以构造函数f[x][y]表示状态x向状态y转移有多少种合法的连接方式
初始函数g[x]是一个行向量，每个位置代表一个初始状态
这样就可以做了........最后输出A[1][1]即可
#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 ",A.num[1][1]); return 0; }