[ZROI CSP七连测Day1] 华二 题解

__vector__ · 2022-08-30 20:08:39 · 个人记录

做法

分类讨论。

经简单计算得知，1,5,7 可以随意交换，也就是说插在哪里都可以，所以先忽略它们的存在。

剩下的数 2,3,4,6,8,9 中，6 不能与其他任何数交换，也就是说 6 的位置是固定的，相当于把序列分成了好几段。

再剩下的数 2,3,4,8,9 中，2,4,8 这三个数不能互相交换，3,9 不能互相交换，这样分成了两类，每一类的内部不能互相交换，位置是相对固定的。

所以，本题的做法：

1. 先忽略 1,5,7 的存在，并用 6 将数列分成一些段。
2. 对于每一段，设 x,y 分别代表第一，二类的元素数量，由于每一类的内部相对位置是固定的，所以答案就是在总共 x+y 个元素中选出 x 个元素作为第一类元素的位置（当然换成选 y 个作为第二类元素的位置也是可以的），答案就是 C_{x+y}^x。
3. 求出每一段的答案后，拼起来。
4. 然后考虑将 1,5,7 插入的方案数，直接算就行，这个答案就很显然了。

Code

#include <bits/stdc++.h>
using namespace std;
namespace Main
{
    typedef long long ll;
    const ll mod=998244353;
    const int maxn=1e5+5;
    inline int read()
    {
        int x=0;
        char ch=getchar();
        while(isdigit(ch))
        {
            x=(x<<1)+(x<<3)+(ch^48);
            ch=getchar();
        }
        return x;
    }
    int n;
    int a[maxn];
    int _c1,_c5,_c7;
    int _cla1,_cla2; 
    ll fact[maxn];
    ll ksm(ll a,ll b)
    {
        ll ret=1;
        while(b)
        {
            if(b&1)ret=ret*a%mod;
            a=a*a%mod;
            b>>=1;
        }
        return ret;
    }
    ll inv(ll a)
    {
        return ksm(a,mod-2);
    }
    inline ll C(int n,int m)
    {
        if(m>n)return 0;
        return fact[n]*inv(fact[m])%mod*inv(fact[n-m])%mod;
    }
    void main()
    {
        n=read();
        for(int i=1;i<=n;i++)
        {
            a[i]=read();
            _c1+=(a[i]==1);
            _c5+=(a[i]==5);
            _c7+=(a[i]==7);
        }
        fact[0]=1;
        for(int i=1;i<=n;i++)
        {
            fact[i]=fact[i-1]*i%mod;
        }
        int l=1;
        ll ans=1;
        for(int i=1;i<=n;i++)
        {
            if(a[i]==2||a[i]==4||a[i]==8)_cla1++;
            if(a[i]==3||a[i]==9)_cla2++;
            if(a[i]==6)
            {
                ans*=C(_cla1+_cla2,_cla1);
                ans%=mod;
                _cla1=_cla2=0;
            }
        }
        if(_cla1||_cla2)
        {
            ans*=C(_cla1+_cla2,_cla1);
            ans%=mod;
        }
        ans=ans*C(n,_c1)%mod*C(n-_c1,_c5)%mod*C(n-_c1-_c5,_c7)%mod;
        printf("%lld",ans);
    }
}
int main()
{
    Main::main();
    return 0;
}