当前位置：首页 > article >正文

1879 C. Make it Alternating

article 2025/3/15 5:36:14

n个01字符串，能够删除若干次，使得字符串变成01相间，即没有两个一样的连续字符。如何删除使其最长，并且得到该最长的字符串所删除的顺序可能组合数有多少种。

对于每个相邻的字符串我们视为一个block，其长度为len，总共k个block，并且对于每个block我们只能保留1个数字，那么最后的结果就是 $\prod_i^k len_i$ ，最后我们把要删除的数字拿出来，做一个全排列，代表他们删除的可能即可，最终结果

$(\prod_i^k len_i) * (\sum_i^k (len_i - 1)!$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353;
ll jc [200005] = {1};
void solve()
{
    string s;
    cin >> s;
    ll res = 1, cnt = 0;
    for (int i = 0; i < s.length();)
    {
        int j = i;
        while (j < s.length() && s[j] == s[i])
        {
            j++;
        }
        int k = j - i;
        res = res * k % mod;
        cnt += (k - 1);
        i = j;
    }
    cout << cnt << " " << res * jc[cnt] % mod << "\n";
}

int main()
{
    for (int i = 1; i <= 1e5; i++)
    {
        jc[i] = jc[i - 1] * i % mod;
    }
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}