P11285 题解

考虑只保留一个前缀，截取出的回路的一部分的结构。不难发现只有最后

k

个可能会向外延伸，且有一些会匹配上。

这引导我们去设计

dp_{i,S}

，表示看到前

i

个位置，后

k

个位置的状态为

S

。注意，这里状态包含有哪些有向外延伸/向外延伸多远，以及只保留前缀后哪两个端点会连接上。

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

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

总复杂度

O(n|T|+\operatorname{poly}(|S|))

，其中

S

为状态集合，

T

为转移集合，可以通过。

CPP

#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;
}

文章操作

相关推荐

评论

P11285 题解