本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 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;
}