题解：P5392 [Cnoi2019] 雪松树之约

· · 题解

好题。

发现 x 很小，想到状压 DP；发现 L 很大，但每一层只会受到上一层的约束，想到矩乘优化转移。时间复杂度 O(k^3\log L)，其中 k 是所有合法的状态数。

当 L=11 时，k=199，可以通过 50 分。而 L=17 时，k=3571，过不去，提示我们还需要进一步压缩状态。

发现每一层是环状的，考虑把旋转全等的状态压到一起。压完之后，从状态 i 到状态 j 的转移就是 i 的所有非本质相同的旋转向 j 的合法转移数量，然后就做完了。

此时当 L=17 时，k=211，可以通过本题。

:::success[Code]

#include<bits/stdc++.h>
#define For(i,j,k) for(int i=j;i<=k;i++)
#define dFor(i,j,k) for(int i=j;i>=k;i--)
using namespace std;
#define MAXN 256
#define Mod 998244353
inline int md(const int &x){
    if(x>=Mod) return x-Mod;
    else return x;
}
long long L;
int x,n,m;
vector<int> v,fa,t;
int find(int x){
    if(fa[x]==x) return x;
    else return fa[x]=find(fa[x]);
}
struct Mat{
    int f[MAXN][MAXN];
    Mat(){
        memset(f,0,sizeof(f));
    }
};
Mat operator *(const Mat &x,const Mat &y){
    Mat ans;
    For(i,0,m-1){
        For(k,0,m-1){
            int t=x.f[i][k];
            For(j,0,m-1){
                ans.f[i][j]=md(ans.f[i][j]+1ll*t*y.f[k][j]%Mod);
            }
        }
    }
    return ans;
}
inline int rotate(int s,int k){
    return (s>>k)|((s&((1<<k)-1))<<(x-k));
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>L>>x;
    For(s,0,(1<<x)-1){
        bool flag=1;
        For(i,0,x-1){
            int j=(i+1)%x;
            if((s&(1<<i))&&(s&(1<<j))){
                flag=0;
                break;
            }
        }
        if(flag){
            v.push_back(s);
        }
    }
    n=v.size();
    fa.resize(n);
    For(i,0,n-1){
        fa[i]=i;
    }
    For(i,0,n-1){
        For(j,0,n-1){
            if(rotate(v[i],1)==v[j]){
                fa[find(i)]=find(j);
            }
        }
    }
    For(i,0,n-1){
        if(fa[i]==i){
            t.push_back(v[i]);
        }
    }
    m=t.size();
    Mat base,tran;
    base.f[0][0]=1;
    For(i,0,m-1){
        For(j,0,m-1){
            For(k,0,x-1){
                if(k!=0&&rotate(t[i],k)==t[i]) break;
                if(rotate(t[i],k)&t[j]) continue;
                tran.f[i][j]++;
            }
        }
    }
    L++;
    while(L){
        if(L&1){
            base=base*tran;
        }
        tran=tran*tran;
        L>>=1;
    }
    cout<<base.f[0][0]<<endl;
    return 0;
}

:::