「NOI2007」生成树计数

轮廓线+矩阵快速幂

Statement

P2109 [NOI2007] 生成树计数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

Solution

观察到 \(k\) 小 \(n\) 大，知道最后肯定是一个矩阵快速幂的方式

设 \(f[i][s]\) 表示第 \(i\) 个点，前 \(i\) 个点的联通状态为 \(s\) 的方案数

发现我们根本不关心无法与 \(i\) 联通的数，所以我们设 \(f[i][s]\) 表示第 \(i\) 个点，\(i-k+1\dots i\) 的连通状态

爆搜发现 \(s\) 只有 \(52\) 种，好耶

由于 \(k\) 太小了，直接 \(2^k\) 暴力枚举 \(i+1\) 怎么连边，\(O(k)\) 转移

转移的时候需要注意：\(???1, …, ?????\) 这 \(??\) 个点，任何一个连通块，
\(??\) 最多只能与其中的一个点相连，这样可以避免环的出现．

如果 \(?????\) 在轮廓线上为一个单独的连通块，那么 \(??\) 必然与 \(?????\) 相连，
这样可以避免出现孤立的连通块

容易写出转移矩阵，\(f[k]\) 单独算一下即可

复杂度 \(O(T^3\log n)\) ,\(T=52\)

Code

#include
using namespace std;
typedef long long ll;
const int mod=65521;

char buf[1<<23],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
ll read(){
    ll s=0,w=1; char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')w=-1; ch=getchar();}
    while(isdigit(ch))s=s*10+(ch^48),ch=getchar();
    return s*w;
}
void inc(int &a,int b){a=a>=mod-b?a-mod+b:a+b;}
void dec(int &a,int b){a=a>=b?a-b:a+mod-b;}

struct Matrix{
    ll mat[55][55];
    Matrix(int o=0){
        memset(mat,0,sizeof(mat));
        if(o)for(int i=0;i<55;++i)mat[i][i]=1;
    }
    Matrix operator*(const Matrix& rhs)const{
        Matrix res;
        for(int i=0;i<55;++i)
            for(int j=0;j<55;++j)
                for(int k=0;k<55;++k)
                    (res.mat[i][j]+=mat[i][k]*rhs.mat[k][j]%mod)%=mod;
        return res;
    }
}mat,f;
int a[15],b[15],fa[15],id[12346];
int cnt[15],cnt2[15],num[15];
int k,tot;
ll n;

Matrix ksm(Matrix a,ll b){
    Matrix res(1);
    while(b){
        if(b&1)res=res*a;
        a=a*a,b>>=1;
    }
    return res;
}
int encode1(){
    int res=0;
    for(int i=1;i<=k;++i)
        res=res*10+a[i];
    return res;
}
int encode2(){
    memset(num,-1,sizeof(num)); 
    int p=0,res=0;
    for(int i=1;i<=k;++i){
        if(num[b[i]]==-1)num[b[i]]=++p;
        res=res*10+num[b[i]];
    }
    return res;
}

void dfs(int pos,int mx){
    if(pos==k+1) return id[encode1()]=++tot,void();
    for(int i=1;i<=mx+1;++i)a[pos]=i,dfs(pos+1,max(mx,i));
}
void solve(int pos,int mx){
    if(pos==k+1){
        memset(cnt,0,sizeof(cnt));
        for(int i=1;i<=k;++i)cnt[a[i]]++;
        for(int s=0;s<(1<>i)&1);  
            bool fg=false;
            for(int i=1;i<=k;++i)
                if(cnt2[i]>=2)fg=true;
            fg|=(cnt[a[1]]==1&&!cnt2[a[1]]);
            if(fg)continue;
            int col=k+1;
            for(int i=0;i>i)&1){
                    if(col==k+1)col=b[i+1];
                    else{
                        int x=b[i+1];
                        for(int j=1;j<=k;++j)
                            if(b[j]==x)b[j]=col;
                    }
                }
            for(int i=1;i<=k;++i)b[i-1]=b[i]; b[k]=col;
            // cout<