NOIP2023模拟9联测30-华二

本文主要是介绍NOIP2023模拟9联测30-华二，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

$\text{Ayano}$ 喜欢 GCD。

现在她有一个长度为 $n$ 的数列 $A=(a_1,⋯,a_n)$ ，其中 $1\leq a_i \leq 9$ 。对于其中相邻的两项的 $a_i$ 和 $a_{i+1}$ ，满足 $gcd(a_i,a_{i+1})=1$ 时， $\text{Ayano}$ 可以通过一次操作交换 $a_i$ 和 $a_{i+1}$ $(1 \leq i \leq n - 1)$ 。

请你计算 $\text{Ayano}$ 可以通过这个操作得到多少种数列（包含原数列） $\pmod {998244353}$ 。

观察当两个数互质时有什么性质。发现当一个数等于 $1, 5, 7$ 时，与其他数都互质，可以随意移动；等于 $2, 4, 8$ 时，其实和 $2$ 差不多（都是 $2$ 的幂），把它们都看作 $2$ ，它们不能跨越，相对顺序是不变的。等于 $3, 9$ 时，看做 $3$ ，而等于 $6$ 时，因为它同时是 $2$ 和 $3$ 的倍数， $2, 3$ 都不能越过它。

记 $n_x$ 表示 $x$ 的出现次数，注意 $2, 4, 8$ 是看做 $2$ 的。

由上面分析，可以先安排好 $1, 5, 7$ 的位置，方案数为 $\dbinom{n}{n_1}\dbinom{n-n_1}{n_5}\dbinom{n-n_1-n_5}{n_7}$ ；然后将剩下的空位拼在一起，看任意两个 $6$ 之间的 $2, 3$ 能怎么排列，若 $n_2,n_3$ 是这两个 $6$ 之间 $2, 3$ 的个数，显然方案数为 $\dbinom{n_2+n_3}{n_2}$ 。都乘在一起，就是答案。

时间复杂度 $O (n)$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr ll mod=998244353;
const int N=1e5+1;
int n,a[N],num2,num3,cnt,num1,num5,num7;
ll f[N],inv[N],ans=1;
ll ksm(ll a,ll b)
{ll ans=1;while(b){if(b&1) ans=ans*a%mod;b>>=1;a=a*a%mod;}return ans;
}
ll C(int n,int m)
{if(n<0||m<0||n<m) return 0;return f[n]*inv[m]%mod*inv[n-m]%mod;
}
int main()
{freopen("b.in","r",stdin);freopen("b.out","w",stdout);scanf("%d",&n);f[0]=1;for(int i=1;i<=n;i++) f[i]=f[i-1]*i%mod;inv[n]=ksm(f[n],mod-2);for(int i=n-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;for(int i=1;i<=n;i++) scanf("%d",&a[i]);a[++n]=6;cnt=1;int sum=0;for(int i=1;i<=n;i++){if(a[i]==6){sum+=num2+num3;ans=ans*C(num2+num3,num2)%mod;cnt++;num2=0,num3=0;}else{if(a[i]%2==0) num2++;else if(a[i]%3==0) num3++;else if(a[i]==1) num1++;else if(a[i]==5) num5++;else if(a[i]==7) num7++;}}cout<<ans*C(n-1,num1)%mod*C(n-1-num1,num5)%mod*C(n-1-num1-num5,num7)%mod;
}