2019江苏省队集训Day6T2

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

Description

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

$ f(s)=\sum_{i=0}^{\frac{|s|}{2}-1}\left[s_{i}=s_{|s|-1-i}\right]$

其中$[x = y] $是个函数, 其定义为

$[x=y]=\left\{\begin{array}{ll}{1,} & {x=y} \\ {0,} & {x \neq y}\end{array}\right.$

读入一个串01 串S , 记其所有非空子序列构成的多重集为$P(S)$. 比如$S = 010$,
那么$P(S) = [0; 1; 0; 01; 00; 10; 010]$. S 一共有$2^{|S|-1} $个不同的非空子序列, 于是有
$|P(S )| = 2^{|S|-1}$ .
求$\sum_{s\in P(S )} f (s)$ 对$998244353 $取模后的值.
比如对于$S = 010$, 答案为$f (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 $中。
输出$\sum_{s\in P(S)}f(s)$对$998244353 $取模后的值.

Sample Input

1
010

Sample Output

1
2

Solution

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

贪心即可。

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

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

李超树板子。

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

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

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

原文地址

那么就应该是

NTT即可。

搞出来卷积即可。

NTT板子。

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

。。。

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

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

然后枚举一对$A,\ B\ 使得\ S[A]==S[n-B-1]\ (0base)$,它们对答案的贡献就是左右各自选相等的若干个,中间的$n-2-A-B$个任意选或者不选,则有

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

代码里字符串是1base

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#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;
}