2019江苏省队集训Day6T2

【2019 江苏省队第一轮集训】D6T2 计数

Description

对于一个01 串s, 定义f (s) 为.

其中是个函数, 其定义为

读入一个串01 串S , 记其所有非空子序列构成的多重集为. 比如, 那么. S 一共有$2^{|S|-1} |P(S )| = 2^{|S|-1}$ . 求 对$998244353 S = 010f (0) + f (1) + f (0) + f (01) + f (00) + f (10) + f (010) =0 + 0 + 0 + 0 + 1 + 0 + 1 = 2$.

Input

从文件$count.in S$ .

Output

输出到文件$count.out _{sP(S)}f(s)998244353 $取模后的值.

Sample Input

010

Sample Output

2

Solution

如果按照神仙的题解方式：

贪心即可。

————《衍芃福音——雅礼集训》第1章——矩阵

搞出来 dp 就行。 ————《衍芃福音——雅礼集训》第3章——水箱

李超树板子。

————《衍芃福音——雅礼集训》第3章——线段游戏

该怎么 dp 怎么 dp 就行了吧。

————《衍芃福音——雅礼集训》第10章——数列

原文地址

那么就应该是

NTT即可。

搞出来卷积即可。

NTT板子。

该怎么卷积就怎么卷积就行了吧。

。。。

还是写点我等凡人能看懂的题解：=.=

有一个套路式子（我考场上就不会太菜了）

然后枚举一对，它们对答案的贡献就是左右各自选相等的若干个，中间的个任意选或者不选，则有 $$ $$

这下可以说该怎么卷积就怎么卷积了

代码里字符串是1base

Code

#include<bits/stdc++.h>
#define ll long long
#define FIO "count"
#define mul3(a,b,c) mul(mul(a,b),c)
using namespace std;

const int N=2.5e5+5,MOD=998244353,P=19;

inline int add(int a,const int &b){if((a+=b)>=MOD)a-=MOD;return a;}
inline int sub(int a,const int &b){if((a-=b)<		0)a+=MOD;return a;}
inline int mul(const int &a,const int &b){return 1ll*a*b%MOD;}
inline int sqr(const int &a){return mul(a,a);}
inline int& inc(int &a,const int &b){return a=add(a,b);}
inline int& dec(int &a,const int &b){return a=sub(a,b);}
inline int& pro(int &a,const int &b){return a=mul(a,b);}
inline int qpow(int a,int b){int c=1;for(;b;b>>=1,pro(a,a))if(b&1)pro(c,a);return c;}

int fac[N],inv[N],invc[N],bin[N],invb[N];
int w[2][1<<P],rev[1<<P];
inline int C(const int &a,const int &b){return a>=b?mul3(fac[a],invc[b],invc[a-b]):0;}

int n,ans;
inline void pre(){
	fac[0]=fac[1]=inv[0]=inv[1]=invc[0]=invc[1]=bin[0]=invb[0]=1;
	bin[1]=2;invb[1]=MOD+1>>1;
	for(int i=2;i<=n;i++)fac[i]=mul(fac[i-1],i),inv[i]=mul(inv[MOD%i],MOD-MOD/i),invc[i]=mul(invc[i-1],inv[i]),bin[i]=mul(bin[i-1],2),invb[i]=mul(invb[i-1],invb[1]);
	for(int i=1;i<1<<P;i<<=1){
		w[0][i]=w[1][i]=1;
		int wn1=qpow(3,(MOD-1)/(i<<1)),wn0=qpow(wn1,MOD-2);
		for(int j=1;j<i;j++)
			w[0][i+j]=mul(w[0][i+j-1],wn0),w[1][i+j]=mul(w[1][i+j-1],wn1);
	}
}

inline void ntt(int *f,int opt,int l){
	for(int i=0;i<l;i++){rev[i]=rev[i>>1]>>1|(i&1)*l>>1;if(i<rev[i])swap(f[i],f[rev[i]]);}
	for(int i=1;i<l;i<<=1)
		for(int j=0;j<l;j+=i<<1)
			for(int k=0;k<i;k++){
				int x=f[j+k],y=mul(f[i+j+k],w[opt][i+k]);
				f[j+k]=add(x,y);
				f[i+j+k]=sub(x,y);
			}
	if(opt)for(int i=0,inv=qpow(l,MOD-2);i<l;i++)pro(f[i],inv);
}

char s[N];

#define poly vector<int>

inline void out(const poly &a){
	for(int i=0,n=a.size();i<n;i++)printf("%d%c",a[i],i^n-1?' ':'\n');
}

inline poly operator*(poly a,poly b){
	int n=a.size(),m=b.size(),l=1;
	while(l<n+m)l<<=1;
	a.resize(l);b.resize(l);
	ntt(&a[0],0,l);ntt(&b[0],0,l);
	for(int i=0;i<l;i++)pro(a[i],b[i]);
	ntt(&a[0],1,l);
	a.resize(n+m-1);
	return a;
}

inline poly& operator *=(poly &a,const poly &b){return a=a*b;}

int main(){
	freopen(FIO".in","r",stdin);
	//freopen(FIO".out","w",stdout);
	scanf("%s",s+1);
	n=strlen(s+1);
	pre();
	poly f,g;
	for(int val=0;val<2;val++){
		f.clear();
		g.clear();
		f.resize(n);
		g.resize(n);
		for(int i=0;i<n;i++)f[i]=(s[i+1]==val+'0')?invc[i]:0,g[i]=(s[n-i]==val+'0')?invc[i]:0;
		f*=g;
		f.resize(n);
		for(int k=0;k<n-1;k++)
			inc(ans,mul3(f[k],fac[k],invb[k]));
	}
	printf("%d\n",mul(ans,bin[n-2]));
	return 0;
}