P11285 题解

· · 题解

考虑只保留一个前缀，截取出的回路的一部分的结构。不难发现只有最后 k 个可能会向外延伸，且有一些会匹配上。

这引导我们去设计 dp_{i,S}，表示看到前 i 个位置，后 k 个位置的状态为 S。注意，这里状态包含有哪些有向外延伸/向外延伸多远，以及只保留前缀后哪两个端点会连接上。

搜一下发现状态数充分小，允许我们这么 dp。

转移是容易的，只需要枚举新一个位置是连接了两个前面的，一个前面的一个后面的，还是两个后面的。可以预处理所有转移然后暴力找转移后的状态的编号。注意除非是最后一个，不可以连接两个本来在前缀已经连接上的端点。

总复杂度 O(n|T|+\operatorname{poly}(|S|))，其中 S 为状态集合，T 为转移集合，可以通过。

#include <bits/stdc++.h>
#define int long long
#define mid ((l+r)>>1)
#define lowbit(i) (i&(-i))
#define mkp make_pair
using namespace std;
const int mod=1e9+7;
inline void add(int &i,int j){
    i+=j;
    if(i>=mod) i-=mod;
} 
int n,K; string s;
vector<int> a;
vector<int> sta[205];
int totsta;
bool cend[205];
map<vector<int>,int> mp;
int mv[205];
vector<int> trans[205];
void dfs(int lev){
    if(lev==K+1){
        sta[++totsta]=a;
        mp[a]=totsta;
        return ;
    }
    a[lev]=0,dfs(lev+1);
    a[lev]=lev,dfs(lev+1);
    for(int i=1;i<lev;i++){
        if(a[i]==i){
            bool fd=0;
            for(int j=i+1;j<lev;j++) fd|=(a[j]==i);
            if(!fd) a[lev]=i,dfs(lev+1);
        }
    }
}
int dp[2][205];
signed main(){
    cin>>n>>K>>s; a.resize(K+1);
    dfs(1); //cout<<totsta<<"\n";
    for(int i=1;i<=totsta;i++){
        vector<array<int,2>> pr;
        for(int j=1;j<=K;j++){
            if(sta[i][j]==j){
                int ot=j;
                for(int l=j+1;l<=K;l++) if(sta[i][l]==j) ot=l;
                pr.push_back({j,ot});
            }
        }
        //end 2
        {
            if(pr.size()==1) trans[i].push_back(0);
            for(int j=0;j<pr.size();j++){
                for(int k=j+1;k<pr.size();k++){
                    for(int x=0;x<2;x++){
                        if(x&&pr[j][0]==pr[j][1]) continue;
                        for(int y=0;y<2;y++){
                            if(y&&pr[k][0]==pr[k][1]) continue;
                            vector<int> tr=sta[i];
                            tr[pr[j][x]]=tr[pr[k][y]]=0;
                            tr[pr[j][x^1]]=tr[pr[k][y^1]]=min(pr[j][x^1],pr[k][y^1]);
                            if(tr[1]) continue;
                            for(int p=1;p<K;p++) tr[p]=tr[p+1]?tr[p+1]-1:0; tr[K]=0;
//                          if(i==10){
//                              for(auto t:tr) cout<<t<<" "; cout<<" ";
//                              cout<<mp[tr]<<"\n";
//                          }
                            trans[i].push_back(mp[tr]);
                        }
                    }
                }
            }
        }
        //chain 1
        {
            for(int j=0;j<pr.size();j++){
                for(int x=0;x<2;x++){
                    if(x&&pr[j][0]==pr[j][1]) continue;
                    vector<int> tr=sta[i];
                    tr[pr[j][x]]=0;
                    tr[pr[j][x^1]]=pr[j][x^1];
                    if(tr[1]) continue;
                    int pp=pr[j][x^1]-1;
                    for(int p=1;p<K;p++) tr[p]=tr[p+1]?tr[p+1]-1:0; tr[K]=pp;
                    trans[i].push_back(mp[tr]);
                }
            }
        }
        //start 2
        {
            vector<int> tr=sta[i];
            if(!tr[1]){
                for(int p=1;p<K;p++) tr[p]=tr[p+1]?tr[p+1]-1:0; tr[K]=K;
                trans[i].push_back(mp[tr]);
            }
        }
        //move
        {
            mv[i]=201;
            vector<int> tr=sta[i];
            if(!tr[1]){
                vector<int> tr=sta[i];
                for(int p=1;p<K;p++) tr[p]=tr[p+1]?tr[p+1]-1:0; tr[K]=0;
                mv[i]=mp[tr];
            }
        }
//      for(int j=1;j<=K;j++) cout<<sta[i][j]<<" "; cout<<" "; for(auto v:trans[i]) cout<<v<<" "; cout<<" "<<mv[i]<<"\n";
    }
    dp[0][1]=1;
    for(int i=1;i<=n;i++){
        memset(dp[i&1],0,sizeof(dp[i&1]));
        if(s[i-1]=='1') for(int j=0;j<=totsta;j++) add(dp[i&1][mv[j]],dp[(i&1)^1][j]);
        else for(int j=0;j<=totsta;j++) for(auto v:trans[j]) add(dp[i&1][v],dp[(i&1)^1][j]);
    }
    cout<<dp[n&1][0]*2%mod;
    return 0;
}