原文链接www.cnblogs.com/zhouzhendong/p/AGC020E.html

前言

真 \(\cdot\) 信仰型动态规划

题解

我们可以采用信仰型动态规划解决此题。

设 \(dp[S]\) 表示 S 这个字符串的所有子集可以被编码成多少种。

那么分两种情况转移：

不编码，答案是子集总数。
考虑枚举最左边的一处编码，递归DP。

时间复杂度 \(O(信仰)\) 。

时间复杂度证明？详见官方题解。反正我没去看。

代码

#include <bits/stdc++.h>

#define clr(x) memset(x,0,sizeof x)

#define For(i,a,b) for (int i=(a);i<=(b);i++)

#define Fod(i,b,a) for (int i=(b);i>=(a);i--)

#define fi first

#define se second

#define pb(x) push_back(x)

#define mp(x,y) make_pair(x,y)

#define outval(x) cerr<<#x" = "<<x<<endl

#define outtag(x) cerr<<"---------------"#x"---------------"<<endl

#define outarr(a,L,R) cerr<<#a"["<<L<<".."<<R<<"] = ";\

						For(_x,L,R)cerr<<a[_x]<<" ";cerr<<endl;

using namespace std;

typedef long long LL;

LL read(){

	LL x=0,f=0;

	char ch=getchar();

	while (!isdigit(ch))

		f|=ch=='-',ch=getchar();

	while (isdigit(ch))

		x=(x<<1)+(x<<3)+(ch^48),ch=getchar();

	return f?-x:x;

}

typedef __int128 LG;

const int N=105,mod=998244353;

int Pow(int x,int y){

	int ans=1;

	for (;y;y>>=1,x=(LL)x*x%mod)

		if (y&1)

			ans=(LL)ans*x%mod;

	return ans;

}

void Add(int &x,int y){

	if ((x+=y)>=mod)

		x-=mod;

}

void Del(int &x,int y){

	if ((x-=y)<0)

		x+=mod;

}

int Add(int x){

	return x>=mod?x-mod:x;

}

int Del(int x){

	return x<0?x+mod:x;

}

int n;

char s[N];

int a[N];

int pw2[N];

map <LG,int> dp,vis;

void write(LG x){

	if (x>9)

		write(x/10);

	putchar('0'+x%10);

}

LG Get(LG a,int L,int R){

	return a>>L&(((LG)1<<(R-L+1))-1);

}

int DP(LG K){

	if (vis[K])

		return dp[K];

	vis[K]=1;

	int ans=0,k=K>>n;

	if (!k)

		return dp[K]=1;

	LG S=Get(K,0,n-1);

	For(i,0,k-1)

		if (S>>i&1)

			ans++;

	ans=pw2[ans];

	int cnt=0;

	For(i,0,k-1){

		For(j,i,k-1){

			int len=j-i+1;

			if (j+len>k-1)

				break;

			LG v=Get(S,i,j);

			for (int t=i+len;t+len-1<k;t+=len){

				v&=Get(S,t,t+len-1);

				Add(ans,(LL)pw2[cnt]*DP(v|(LG)len<<n)%mod

						*DP(Get(S,t+len,k-1)|(LG)(k-(t+len))<<n)%mod);

			}

		}

		if (S>>i&1)

			cnt++;

	}

	return dp[K]=ans;

}

int main(){

	cin>>s;

	n=strlen(s);

	pw2[0]=1;

	For(i,1,n)

		pw2[i]=Add(pw2[i-1]<<1);

	For(i,0,n-1)

		a[i]=s[i]-'0';

	LG S=0;

	For(i,0,n-1)

		S|=(LG)a[i]<<i;

	S|=(LG)n<<n;

	write(DP(S));

	puts("");

	return 0;

}

巴特西

AtCoder Grand Contest 020 (AGC020) E - Encoding Subsets 动态规划

前言

题解

代码

最新文章

热门文章