CF2255B A Ribbon for Tomorrow-题解

· · 题解

CF2255B A Ribbon for Tomorrow-题解

题目分析

看第一个样例，情况是 00 和 0 可以互换位置；看第二个样例，情况是 00 和 两个 0 可以互换位置（准确来说，是每个连续 0 段长度都可以重新分配）。

考虑怎样进行这种交换。比如 000110000 这个字符串，有贡献操作的 l 和 r 应当在 000 和 0000 中选择，如 l=1 和 r=7 时，操作后字符串是 001100000，两个连续段做到了 0 个数的变化，进而有答案的变化。

关注这个过程中的不变量。可以发现，0 的总数、连续 0 的段数都没有变化。结合上面的交换，对 0 我们可以描述为，将 cnt 个 0 放入 seg 个连续段的方案，用隔板法容易得到 \dbinom{cnt-1}{seg-1} 。

对于 1 也是同理。将两个字符的排列方式用乘法原理即为最终答案。

代码实现

注意当某个字符的 cnt 为 0 时的特判。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define db double
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
const int N=1e6+10;
int inv[N];
int ji[N];
const int mod=998244353;
int qpow(int a,int b)
{
    int ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans%mod;
}
int c(int a,int b)
{
    if(b<0) return 0;
    return ji[a]*inv[b]%mod*inv[a-b]%mod;
}
signed main()
{
    int sti=clock();

//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ji[0]=1;inv[0]=1;
    for(int i=1;i<=N-10;i++)
    {
        ji[i]=ji[i-1]*i%mod;
    }
    inv[N-10]=qpow(ji[N-10],mod-2);
    for(int i=N-11;i>=1;i--)
    {
        inv[i]=inv[i+1]*(i+1)%mod;
    }
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        string s;
        cin>>s;
        s=" "+s;
        int cnt0=0;int cnt1=0;int seg0=0;int seg1=0;
        for(int i=1;i<=n;i++)
        {
            if(s[i]=='1') cnt1++;
            else cnt0++;

            if(i==1 || s[i]!=s[i-1]) 
            {
                if(s[i]=='1') seg1++;
                else seg0++;
            }
        }
        int ans0=(cnt0==0 ? 1 : c(cnt0-1,seg0-1));
        int ans1=(cnt1==0 ? 1 : c(cnt1-1,seg1-1));

        cout<<ans0*ans1%mod<<'\n';

     } 

//  cerr<<1.0*(clock()-sti)/CLOCKS_PER_SEC<<endl;
    return 0;
}