题解：AT_arc189_a [ARC189A] Reversi 2

· · 题解

题外：校内模拟赛打这个题糖丸了，没处理 n=1 的情况，还没处理最后一段同色段，导致 100 \to 0。

Solution

首先由题目得，当 a_1 和 a_n 不是初始值时无解，输出 0。

定义一个极大同色段为目标序列中一段连续相同的数，并且无法再向左或向右扩展。

显然，只要有一个极大同色段的长度是偶数，就不可能实现，输出 0。

然后题目中这个操作可以看成是把一个不在两边的极大同色段的值反转，然后和两侧的极大同色段合并。因为一个极大同色段内部对合并没有影响，所以可以看成一个值。

然后我们来看一下每种序列变成一个极大同色段有多少种操作方案数：

对于 \texttt 101：反转 \texttt 0，有 1 种操作方案；

对于 \texttt 10101：依次反转两个 \texttt 0，有 2 种；或者先把中间的 \texttt 1 反转成 \texttt 0，再把中间三个 \texttt 0 反转成 \texttt 1，一共有 3 种；

对于 \texttt 1010101：现在序列变长了，好像不能再枚举答案了。这时我们发现：只要从中间选一个数反转，忽略极大同色段之后就变成了上一种情况，而上一种情况的方案数我们是知道的！这就意味着我们可以通过递推获取所有长度的答案。选择第一个数的方案数有 5 种，所以现在的方案数共有 5 \times 3 = 15 种。

综上所述，可以列出转移方程：设 dp_i 表示长度为 i 的序列全部合并的方案数，则有 dp_i = dp_{i-2} \times (i - 2)。

当 i = 1 时，未避免讨论，规定 dp_1 = 1 表示长度为 1 的序列合法。经验证，发现 dp_3 = dp_1 \times (3 - 1)。

现在知道了方案数，但对于一个序列还有不同的操作步骤数。因为不同的极大同色段的步骤可以相互交错，但是同一个段内部的步骤必须依次给出。

这就好像是有一排气球，对于每列气球都只能先射底部的气球，问有多少种方案可以射完全部气球。（思路由 @_Largestbug 提供。）如果不考虑每一列的限制，一共有 sum! 种；但是我们需要去掉每一列的全排列，所以共有 \frac {sum!}{\prod_{i=1}^{n} (a_i !)} 种。

那么对于一个有 n（n 是奇数）个极大同色段的序列，每次操作会把三个同色段合并为一个，而目标是只剩下一个极大同色段，所以操作步骤数为 \lfloor \frac{n}{2} \rfloor。然后就是上面的处理方法，注意除法取模要用逆元。

Code

AC 记录

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const ll N=200002,MOD=998244353;
int n,a[N],fac=1,inv[N];
ll dp[N],vt[N],sum=0,tot=0,ans=1;
inline ll mo(ll x){return x-x/MOD*MOD;}
inline ll fpow(ll a,ll b){ll ret=1;for(;b;b>>=1){if(b&1)ret=mo(ret*a);a=mo(a*a);}return ret;}
int main(){
    scanf("%d",&n);
    ll cnt=0;
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
        if(i>1&&a[i]!=a[i-1]){
            if(!(cnt&1)){
                printf("0\n");
                return 0;
            }
            cnt=1;
        }
        else
            cnt++;
    }
    if(!(cnt&1)||a[n]!=(n&1)||a[1]==0){
        printf("0\n");
        return 0;
    }
    dp[1]=1;
    for(ll i=3;i<=n;i+=2)
        dp[i]=mo(dp[i-2]*(i-2));//计算方案数
    cnt=0;
    for(int i=1;i<=n;++i){
        if(i>1&&a[i]!=a[i-1]){
            if(cnt==1)
                continue;
            vt[++tot]=cnt/2,sum+=(cnt/2);//统计步骤数对答案影响
            ans=mo(ans*dp[cnt]);//先乘上不同方案数
            cnt=1;
        }
        else
            cnt++;
    }
    if(cnt>1){//一定要处理！就是这里让我挂了100分
        vt[++tot]=cnt/2,sum+=(cnt/2);
        ans=mo(ans*dp[cnt]);
    }
    for(ll i=1;i<=sum;++i)
        fac=mo(fac*i);
    inv[sum]=fpow(fac,MOD-2);
    for(ll i=sum;i;--i)//线性预处理阶乘逆元
        inv[i-1]=mo(inv[i]*i);
    ans=mo(ans*fac);
    for(int i=1;i<=tot;++i)
        ans=mo(ans*inv[vt[i]]);//去掉每个极大同色段操作步骤不同排列的影响
    printf("%lld\n",ans);
    return 0;
}