题解：CF2283E Partition of a Binary String

· · 题解

思路

先考虑这个最大答案是多少。

先注意到一个集合里能有两种元素的情况只能有 010，101，01，10。

根据题目的定义，我们可以把贡献放到每个点上考虑。当前点贡献为 2 当且仅当他所在的集合有两种元素，否则他的贡献为 1。那你就是要使得有两种元素的集合最大。

然后你发现一个元素，只要左边或右边的元素与他不同，他一定可以放进有两种元素的集合，也就是所有 01 交替的子串的元素都能有 2 的贡献。

那你就把能放进两种元素的集合元素都放进去，这样一定最优。

那么现在每个元素到底放有一种集合里还是两种元素集合里是已经确定的，考虑分开算他们的方案数。

对于属于只有一种元素的集合的元素，就是把 0 分成若干个非空集合，把 1 分成若干个非空集合，欸，这不是贝尔数（第二类斯特林数一行之和）吗？这个预处理即可。

对于属于有两种元素的集合的元素，也就是考虑长度为 k 的 01 交替序列的方案，注意到每组长度只能为 2 或 3。你就考虑设 f_k 表示长度为 k 的答案，那么这个就可以从 f_{k-2} 和 f_{k-3} 转移来（即考虑最后一组是 2 个还是 3 个），这个也可以预处理。

最后把这两部分乘起来即可。

代码

#include<bits/stdc++.h>
#define pii pair<int,int>
#define vec vector<int>
#define mat vector<vec>
#define int long long
#define ull unsigned long long
#define ld long double
using namespace std;
int read()
{
    int t=1,x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') t=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return t*x;
}
const int N=5050,mod=998244353;
int S[N][N];

int f[N];

void init(int n)
{
    S[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            S[i][j]=(S[i-1][j-1]+S[i-1][j]*j%mod)%mod;
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<i;j++)
        {
            S[i][i]=(S[i][i]+S[i][j])%mod;//相当于贝尔数
        }
    }
    f[0]=1;//注意f[1]=0
    f[2]=1;
    f[3]=1;
    for(int i=4;i<=n;i++) f[i]=(f[i-2]+f[i-3])%mod;

}
string s;
int n;


void solve()
{
    n=read();
    int ans=0;
    cin>>s;
    s=s[0]+s;//这样写可以不考虑边界问题了
    s=s+s[n];
    int c[2]={0,0};
    int res=1;

    for(int i=1;i<=n;)//双指针求所有极长01交替串
    {
        int l=i;
        while(s[l+1]!=s[l]&&l<n)l++;
        if(l!=i)res=res*f[l-i+1]%mod;
        i=l+1;
    }

    for(int i=1;i<=n;i++)
    {
        if(s[i]!=s[i-1]||s[i]!=s[i+1])
        {
            ans+=2;
        }
        else 
        {
            c[s[i]-'0']++;
            ans++;
        }
    }
    // cout<<c[0]<<" "<<c[1]<<"\n";
    printf("%lld %lld\n",ans,S[c[0]][c[0]]*S[c[1]][c[1]]%mod*res%mod);
}

signed main()
{
    init(N-10);
    int t=read();
    while(t--)
    {
        solve();
    }
    return 0; 
} 
/*


*/