题目描述

给定一个长度为 n 的 01 串，问有多少种划分，使得每一个划分出来的子串的 1 的个数组成的序列是回文的，答案对 998244353 取模。

思路

插板法

可以根据 11 在的位置分块

[01]  [0..0]  [10][0 1] \ \ [0..0]\ \ [1 0]

首尾相应例如1与n,2与n-1… 这些相应块插的板数一定是相同的

设前一个块可以插x个,后一个块可以插y个

就可以贡献 ∑i=0min(x,y)Cxi∗Cyi\sum_{i=0}^{min(x,y)}C_x^i*C_y^i

还有一种特殊情况

[0 1] 0 0 [1 0 0]

类似这种可以分为奇数块中间的部分对答案的贡献就是 2t2^t ,tt 为间隔数

运用乘法原理进行统计，每个对应块均是相互独立的

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
int fac[6050],invfac[6050];
int C(int n,int m)
{
    return n < m ? 0 : (long long)fac[n] * invfac[m] % mod * invfac[n - m] % mod;
}
void init()
{
	// i最大值为数据量
    fac[0]=invfac[0]=invfac[1]=1;
    for(int i=1;i<=6000 + 10;i++)fac[i]=(long long)fac[i-1]*i%mod;
    for(int i=2;i<=6000 + 10;i++)invfac[i]=(long long)(mod-mod/i)*invfac[mod%i]%mod;
    for(int i=2;i<=6000 + 10;i++)invfac[i]=(long long)invfac[i-1]*invfac[i]%mod;
}
int qmi(int a,int b){
    int res = 1;
    while(b){
        if(b&1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
signed main()
{
    init();
    int n;cin>>n;
    vector<int> a(n+1);
    string s;cin>>s;
    for(int i = 0;i < s.size();i++) a[i+1] = s[i] - '0';
    vector<int> p;
    p.push_back(1);
    forr(i,1,n) if(a[i] == 1) p.push_back(i);
    p.push_back(n);
    int res = 1;
    for(int i = 1,j = p.size()-2;;i++,j--){
        int x = p[i] - p[i-1];
        int y = p[j+1]-p[j];
        if(j+2 == i) break;
        if(j+1 == i){
            res = (res * qmi(2,y))%mod;
            break;
        }
        int t = 0;
        for(int k = 0;k <= min(x,y);k++){
            t = (t + C(x,k)*C(y,k))%mod;
        }
        res = res*t%mod;
    }
    cout << res << endl;
    return 0;
}