专栏文章

AGC020E Encoding Subsets 题解

CCoffee_zzz/xin
AT_agc020_e题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minlvf5l
此快照首次捕获于
2025/12/02 04:32
3 个月前
此快照最后确认于
2025/12/02 04:32
3 个月前
查看原文
首先考虑对于一个确定的长度为 nn 的 01\texttt{01} 串 SS，如何求 SS 的编码方式数。
设 fl,rf_{l,r} 表示 Sl∼SrS_l\sim S_r 的编码方式数，gl,rg_{l,r} 表示 Sl∼SrS_l\sim S_r 缩成一个括号或单个字符的编码方式数。
对于 fl,rf_{l,r}，枚举 Sl∼SrS_l\sim S_r 编码后第一个字符的来源，得到转移方程：
fl,r=∑m=lrgl,m×fm+1,rf_{l,r}=\sum_{m=l}^{r} g_{l,m} \times f_{m+1,r}
对于 gl,rg_{l,r}，枚举 Sl∼SrS_l\sim S_r 的循环节 dd，得到转移方程：
gl,r=∑d∣len,d≠lenw(d,l,r)×fl,l+d−1g_{l,r}=\sum_{d\mid len,d \ne len} w(d,l,r) \times f_{l,l+d-1}
其中，len=r−l+1len=r-l+1，若 dd 为 Sl∼SrS_l\sim S_r 的循环节则 w(d,l,r)=1w(d,l,r)=1，否则 w(d,l,r)=0w(d,l,r)=0。
直接计算即可得到 SS 的编码方式数 f1,nf_{1,n}。
接下来考虑如何计算长度为 nn 的 01\texttt{01} 串 SS 的所有子集的编码方式数之和。
同理，设 fSf_S 表示 SS 的所有子集的编码方式数之和，gSg_S 表示 SS 的所有子集的缩成一个括号或单个字符的编码方式数之和。
对于 fSf_S，仍然枚举 SS 编码后第一个字符的来源，得到转移方程：
fS=∑m=1ngS[1,m]×fS[m+1,n]f_S=\sum_{m=1}^{n} g_{S[1,m]} \times f_{S[m+1,n]}
对于 gSg_S，同样枚举 SS 的循环节 dd，得到转移方程：
gS=∑d∣n,d≠nfc(S,d)g_S=\sum_{d \mid n,d \ne n} f_{c(S,d)}
其中 c(S,d)c(S,d) 表示，把 SS 分成长度为 dd 的 nd\dfrac{n}{d} 个 01\texttt{01} 串，每个 01\texttt{01} 串按位与的结果。
记忆化搜索即可。有效状态数并不多，足以通过。
C
const int mod=998244353;
string s;
map <string,int> f,g;
void add(int &a,int b){
	a+=b;
	if(a>=mod) a-=mod;
}
int ad(int a,int b){
	a+=b;
	if(a>=mod) a-=mod;
	return a;
}
int G(string s);
int F(string s){
	if(s=="") return 1;
	if(f.count(s)) return f[s];
	int n=s.size(),ans=0;
	for(int i=1;i<=n;i++) add(ans,1ll*G(s.substr(0,i))*F(s.substr(i,n-i))%mod);
	return f[s]=ans;
}
int G(string s){
	if(s=="") return 1;
	if(s=="0") return 1;
	if(s=="1") return 2;
	if(g.count(s)) return g[s];
	int n=s.size(),ans=0;
	for(int d=1;d<n;d++){
		if(n%d!=0) continue;
		string t="";
		for(int i=0;i<d;i++){
			bool x=1;
			for(int j=i;j<n;j+=d) x&=(s[j]=='1');
			t+=x+'0';
		}
		add(ans,F(t));
	}
	return g[s]=ans;
}
void solve(){
	cin>>s;
	cout<<F(s)<<endl;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...