P10551 [THUPC 2024 决赛] 连向未来 题解

· · 题解

简化版题意：求出一个矩阵，使得可以对这个矩阵划分成若干条链，每条链形如 1,2,3 顺次连接。

首先我们发现这个状态只和上一列有关，因此对于同一列的每个位置，我们有下面几种讨论：

一共 5 种情况，对于一列，最多 3 个数，那么就有 5^3 种情况，我们在判定一个状态的过程中，发现可能有多种匹配的方式，这样的话就需要搜索每一种匹配可不可能达到最终状态（即所有位置都已经匹配）。

这就是 NFA（非确定性有限状态自动机），我们考虑转化为 DFA（确定性有限状态自动机）。

比较暴力的做法就是记录当前状态可能的匹配是哪些，也就是在上面 5^3 个匹配中的一个子集 S，这样的 S 一共有 2^{5^3} 个。

考虑最小化 DFA，一个最简单的做法就是删去从起点开始不可达的状态，我们惊奇的发现，这样的状态只有 46 个！于是我们采用矩阵乘法就可以轻松解决这道题了。

具体的，枚举完当前列的可能的匹配子集 S 后，枚举下一列的每个数具体是多少，然后看这个匹配子集 S 中的每一个匹配和我们枚举的下一列的每个数进行匹配后可能会产生多少种匹配，把这些匹配求交，就是新的 S'。

所有不同的 S 只有 46 个，使用矩阵乘法预处理 2 的次幂，最后询问的时候用向量乘矩阵即可。

为了避免篇幅过长，这里就只放 n=3 时打表的代码：

namespace TYPE_3{
    vector<pair<ll,ll> > op[1005];
    ll ttt,i,j,val[1005],a[1005],b[1005],vis[1005],news[1005],used[1005],idd[1005],s[1005][1005],tot,id2[1005];
    map<ll,ll> maps;
    inline void output(){
        if(news[1]==-1||news[2]==-1||news[3]==-1) return ;
        op[b[1]*100+b[2]*10+b[3]].push_back(make_pair(a[1]*100+a[2]*10+a[3],news[1]*100+news[2]*10+news[3]));
    }
    inline void solve(){
        vis[1] = vis[2] = vis[3] = 0;
        for(ll i=1;i<=3;i++){
            vis[i]=0;
            if(a[i]==1) continue;
            if(a[i]==2||a[i]==3){
                if(b[i]!=2) return ;
                if(a[i]==2) vis[i]=1;
                else vis[i]=2;
            }
            if(a[i]==4){
                if(b[i]!=1) return ;
                vis[i]=3;
            }
            if(a[i]==5){
                if(b[i]!=3) return ;
                vis[i]=4;
            }
        }
        if(vis[1]==1) news[1]=5;
        else if(vis[1]==2) news[1]=4;
        else if(vis[1]==3) news[1]=1;
        else if(vis[1]==4) news[1]=1;
        else if(b[1]==1) news[1]=2;
        else if(b[1]==2) news[1]=-1;
        else news[1]=3;

        if(vis[2]==1) news[2]=5;
        else if(vis[2]==2) news[2]=4;
        else if(vis[2]==3) news[2]=1;
        else if(vis[2]==4) news[2]=1;
        else if(b[2]==1) news[2]=2;
        else if(b[2]==2) news[2]=-1;
        else news[2]=3;

        if(vis[3]==1) news[3]=5;
        else if(vis[3]==2) news[3]=4;
        else if(vis[3]==3) news[3]=1;
        else if(vis[3]==4) news[3]=1;
        else if(b[3]==1) news[3]=2;
        else if(b[3]==2) news[3]=-1;
        else news[3]=3;

        output();

        if((!vis[1]||!vis[2])&&abs(b[1]-b[2])==1){
            if(vis[3]==1) news[3]=5;
            else if(vis[3]==2) news[3]=4;
            else if(vis[3]==3) news[3]=1;
            else if(vis[3]==4) news[3]=1;
            else if(b[3]==1) news[3]=2;
            else if(b[3]==2) news[3]=-1;
            else news[3]=3;
            if(!vis[1]&&!vis[2]){
                if(b[1]==1&&b[2]==2) news[1]=1,news[2]=5;
                if(b[1]==2&&b[2]==1) news[1]=5,news[2]=1;
                if(b[1]==2&&b[2]==3) news[1]=4,news[2]=1;
                if(b[1]==3&&b[2]==2) news[1]=1,news[2]=4;
                output();
            }
            else if(!vis[1]){
                news[1]=1,news[2]=1;
                if(vis[2]==1&&b[1]==3) output();
                if(vis[2]==2&&b[1]==1) output();
            }
            else if(!vis[2]){
                news[1]=1,news[2]=1;
                if(vis[1]==1&&b[2]==3) output();
                if(vis[1]==2&&b[2]==1) output();
            }
        }
        if((!vis[2]||!vis[3])&&abs(b[2]-b[3])==1){
            if(vis[1]==1) news[1]=5;
            else if(vis[1]==2) news[1]=4;
            else if(vis[1]==3) news[1]=1;
            else if(vis[1]==4) news[1]=1;
            else if(b[1]==1) news[1]=2;
            else if(b[1]==2) news[1]=-1;
            else news[1]=3;
            if(!vis[3]&&!vis[2]){
                if(b[3]==1&&b[2]==2) news[3]=1,news[2]=5;
                if(b[3]==2&&b[2]==1) news[3]=5,news[2]=1;
                if(b[3]==2&&b[2]==3) news[3]=4,news[2]=1;
                if(b[3]==3&&b[2]==2) news[3]=1,news[2]=4;
                output();
            }
            else if(!vis[3]){
                news[3]=1,news[2]=1;
                if(vis[2]==1&&b[3]==3) output();
                if(vis[2]==2&&b[3]==1) output();
            }
            else if(!vis[2]){
                news[3]=1,news[2]=1;
                if(vis[3]==1&&b[2]==3) output();
                if(vis[3]==2&&b[2]==1) output();
            }
        }
        if(!vis[1]&&!vis[2]&&!vis[3]){
            if(abs(b[1]-b[2])==1&&abs(b[2]-b[3])==1&&abs(b[1]-b[3])==2){
                news[1]=1,news[2]=1,news[3]=1;
                output();
            }
        }
    }
    inline void dfs(ll x){
        if(x>3){
            for(ll i=1;i<=3;i++){
                for(ll j=1;j<=3;j++){
                    for(ll k=1;k<=3;k++){
                        b[1]=i,b[2]=j,b[3]=k;
                        solve();
                    }
                }
            }
            return ;
        }
        for(ll i=1;i<=5;i++) a[x]=i,dfs(x+1);
    }
    inline void dfs2(ll S){
        if(maps[S]) return ;
        maps[S]=++tot,id2[tot]=S;
        for(ll i=1;i<=3;i++){
            for(ll j=1;j<=3;j++){
                for(ll k=1;k<=3;k++){
                    ll p = i*100+j*10+k,newS = 0;
                    for(ll l=0;l<op[p].size();l++){
                        if(!idd[op[p][l].first]) continue;
                        if(!idd[op[p][l].second]) idd[op[p][l].second]=++ttt;
                        if((S>>idd[op[p][l].first])&1) newS|=(1ll<<idd[op[p][l].second]);
                    }
                    dfs2(newS);
                    s[maps[S]][maps[newS]]++;
                }
            }
        }
    }
    vector<ll> v(0);
    int main(){
        dfs(1);
        idd[111]=++ttt;
        dfs2(2);
        for(i=1;i<=tot;i++) if((id2[i]>>1)&1) v.push_back(i);
        return 0;
    }
}