[AGC020E] Encoding Subsets

CXXVIII.[AGC020E] Encoding Subsets

这种“压缩”题可以考虑区间DP。但是若考虑标准的区间的话它“子集”等定义又不好处理。

于是我们考虑对字符串作DP。设 \(f(S)\) 表示一个串 \(S\) 及其所有子集的压缩方案数。

显然，其有两种转移方式：一种是 \(S_0\) 不压缩，直接从 \(f(S_{1\sim|S|-1})\) 转移过来；一种则是 \(S_0\) 与后面一些东西压缩。

于是我们枚举循环节长度以及循环次数，找到这所有循环串的交集（仍是一个串），然后转移即可。

使用 map 维护DP状态，复杂度玄学，但能过。

代码：

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
string s;
void merge(string &s,string t){//merge string t into s
	for(int i=0;i<s.size();i++)if(t[i]=='0')s[i]='0';
}
map<string,int>mp;
int dfs(string s){
	if(s.empty())return 1;
	if(s.size()==1)return s[0]=='0'?1:2;
	if(mp.find(s)!=mp.end())return mp[s];
	int ret=1ll*dfs(s.substr(0,1))*dfs(s.substr(1))%mod;//encoding the leading character separately 
	for(int i=1;(i<<1)<=s.size();i++){//encoding i charactets together as a permutation chapter 
		string t=s.substr(0,i);
		for(int j=i;j+i<=s.size();j+=i)merge(t,s.substr(j,i)),(ret+=1ll*dfs(t)*dfs(s.substr(j+i))%mod)%=mod;
	}
	return mp[s]=ret;
}
int main(){
	cin>>s;
	printf("%d\n",dfs(s));
	return 0;
}