Atcoder agc020E

这题看上去就有一股乱搞的感觉。
注意到答案显然可以DP，对于一个字符串$S$，我们令$F[S]$代表$S$的所有子集的编码方案数之和。那么考虑最左边被编码的是哪个子串，有$F[S]=(1+[S_1=1])\cdot F[S_{2...|s|}]+{\sum }_{ij\le n}F[S_{1...i}and{S}_{i+1...2i}and...S_{(j-1)i+1...ij}]\cdot F[S_{ij+1...|s|}]$。
直接对这个DP记忆化就能通过了。题解有高超技巧证明状态数目上界是$\mathcal{O}(n^3+2^{\frac{n}{8}})$的，我用了map<string,int>导致巨慢。

#include <bits/stdc++.h>
#define MOD 998244353

using namespace std;

typedef long long ll;

map <string,int> mp;

void merge(string &x,string y) {
  for(int i=0;i<x.length();i++)
    if (y[i]=='0') x[i]='0';
}

int dp(string s) {
  if (s.empty()) return 1;
  if (mp.count(s)) return mp[s];
  int n=s.length(),ans=0;
  ans=(ans+((s[0]=='1')?2LL:1LL)*dp(s.substr(1,n)))%MOD;
  for(int i=1;2*i<=n;i++) {
  	string cur=s.substr(0,i);
  	for(int j=2;i*j<=n;j++) {
  		merge(cur,s.substr(i*(j-1),i*j));
  		ans=(ans+(ll)dp(cur)*dp(s.substr(i*j,n)))%MOD;
	  }
  }
  return mp[s]=ans;
}

int main() {
  string s;
  cin>>s;
  cout<<dp(s)<<endl;
  return 0;
}