| 记录编号 |
85134 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
[NOI 2007]生成树计数 |
最终得分 |
100 |
| 用户昵称 |
 cstdio |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
0.184 s |
| 提交时间 |
2013-12-27 16:05:47 |
内存使用 |
0.37 MiB |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<iomanip>
using namespace std;
typedef long long ll;
const ll MOD=65521;
const int SIZEN=60;
ll N;
int K;
int SNUM;
vector<int> state;
int pow2[21]={1};
void printarray(int *s,int n){//调试接口,输出数组s下标为1~n的元素
for(int i=1;i<=n;i++) cout<<s[i]<<" ";cout<<endl;
}
class MATRIX{
public:
int n,m;//n行m列
ll s[SIZEN][SIZEN];
MATRIX(){//初始化为零
m=n=0;
memset(s,0,sizeof(s));
}
void print(void){//调试接口,输出矩阵
cout<<"size:"<<n<<" "<<m<<endl;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++) cout<<s[i][j]<<" ";
cout<<endl;
}
}
void assign_one(int sn){//赋值为sn行的单位矩阵
n=m=sn;
for(int i=1;i<=n;i++) s[i][i]=1;
}
};
MATRIX operator * (MATRIX a,MATRIX b){//矩阵乘法,结果对MOD取模
MATRIX c;
c.n=a.n;c.m=b.m;
int i,j,k;
for(i=1;i<=c.n;i++){
for(j=1;j<=c.m;j++){
c.s[i][j]=0;
for(k=1;k<=a.m;k++){
c.s[i][j]+=(a.s[i][k]*b.s[k][j])%MOD;
}
c.s[i][j]%=MOD;
}
}
return c;
}
MATRIX quickpow(MATRIX a,ll n,int sn){//a^n,sn行/列
MATRIX ans;ans.assign_one(sn);
while(n){
if(n&1) ans=ans*a;
a=a*a;
n>>=1;
}
return ans;
}
MATRIX M,D;//M是前k项的状态,D是代表转移方法的矩阵
//用八进制储存最小表示法,第i个元素的表示用代表8^i的数位表示
int getdig(int x,int k){//返回最小表示法状态x中代表8^k的数位
return (x>>(3*k))&7;
}
int changedig(int x,int k,int t){//将x代表8^k的八进制位改为t,返回x
x&=~(7<<(3*k));
x|=t<<(3*k);
return x;
}
void printdig(int x){//调试接口,输出x的各个八进制位
for(int i=1;i<=K;i++) cout<<getdig(x,i);
}
void DFS(int x,int t,int s){//搜索,得出K个点所有可能的连通情况
if(x==K){
state.push_back(s);
return;
}
for(int i=1;i<=t;i++) DFS(x+1,t,changedig(s,x+1,i));
DFS(x+1,t+1,changedig(s,x+1,t+1));
}
int ufs[SIZEN]={0};//一个用来储存并查集的数组(虽然函数里都是传地址= =)
int grand(int *ufs,int x){//并查集ufs中x的根节点
return !ufs[x]?x:(ufs[x]=grand(ufs,ufs[x]));
}
void demdl(int *ufs,int K,int s){//解调,将K个节点的状态s表示在ufs中
int temp[SIZEN]={0};
int i,nc;
for(i=1;i<=K;i++){
nc=getdig(s,i);
if(temp[nc]==0) temp[nc]=i,ufs[i]=0;
else ufs[i]=temp[nc];
}
}
int mdl(int *ufs,int K){//调制,将ufs中前K个节点的状态表示为最小表示法
int temp[SIZEN]={0};
int i,g,tot=0;
for(i=1;i<=K;i++){
g=grand(ufs,i);
if(temp[g]==0) temp[i]=temp[g]=++tot;
else temp[i]=temp[g];
}
int ans=0;
for(i=1;i<=K;i++) ans=changedig(ans,i,temp[i]);
return ans;
}
bool check(int *ufs,int K,int cs){//对ufs中已储存的状态(K个点),检查增加一个与前K个点的连边状态用二进制表示为cs的节点后,图中是否有环(没有则返回true)
//这会改变ufs的值
int i,g;
for(i=1;i<=K;i++){
if(cs&pow2[i-1]){
g=grand(ufs,i);
if(g==grand(ufs,K+1)) return false;
ufs[grand(ufs,K+1)]=g;
}
}
return true;
}
void search(int x,int s){//对第x个节点已经确定,状态为s,继续搜索,这将得出前K个点所有连通情况所对应图的个数
if(x==K){
int temp=lower_bound(state.begin(),state.end(),s)-state.begin()+1;
M.s[1][temp]++;
return;
}
int tp[SIZEN]={0};
int i,maxs=pow2[x]-1;//0到maxs,每个数的二进制编码都对应一个节点x+1连的点集
demdl(tp,x,s);//解调到tp中
for(i=0;i<=maxs;i++){
memcpy(ufs,tp,sizeof(tp));
if(check(ufs,x,i)){
search(x+1,mdl(ufs,x+1));
}
}
}
void makestep(int *ufs){//输入时ufs中储存了K+1位的连通状态,函数将后K位的连通状态放在前K个位置以方便调制
//将第1个点的信息放在下标为K+1的位置并相应修改ufs值,这保持了拓扑结构不变
int i,tp=ufs[1];
for(i=2;i<=K+1;i++){
if(ufs[i]==1){
ufs[i-1]=K+1;
}
else if(ufs[i]) ufs[i-1]=ufs[i]-1;
else ufs[i-1]=0;
}
if(tp) ufs[K+1]=tp-1;
else ufs[K+1]=0;
}
void prepare_D(void){//得到转移矩阵D
int i,j,k,maxs=pow2[K]-1;
int tp[SIZEN]={0};
int temp;
D.m=D.n=SNUM;
for(i=1;i<=SNUM;i++){
temp=state[i-1];
demdl(tp,K,temp);
for(j=0;j<=maxs;j++){
memcpy(ufs,tp,sizeof(tp));
if(check(ufs,K,j)){
bool flag=false;
for(k=2;k<=K+1;k++) if(grand(ufs,k)==grand(ufs,1)) flag=true;//必须让第一个节点能连到后面,否则就是不合法的
if(flag){
makestep(ufs);
temp=lower_bound(state.begin(),state.end(),mdl(ufs,K))-state.begin()+1;
D.s[i][temp]++;
}
}
}
}
}
void init(void){
scanf("%d%lld",&K,&N);
for(int i=1;i<=10;i++) pow2[i]=2*pow2[i-1];
DFS(0,0,0);
sort(state.begin(),state.end());//将所有可能的最小表示法排序,以方便查找
SNUM=state.size();//最小表示法的个数
M.n=1,M.m=SNUM;
search(0,0);//这得到了前K项的状态矩阵
prepare_D();//这得到了转移矩阵
}
int main(){
freopen("count.in","r",stdin);
freopen("count.out","w",stdout);
init();
M=M*quickpow(D,N-K,SNUM);//用矩阵乘法加速转移
printf("%lld\n",M.s[1][1]);//因为"所有点均连通"在排序后一定是首个状态
return 0;
}