NOIP2023模拟9联测30 B. 华二
题目大意
有一个数列 \(A = (a_1 ,\cdots ,a_n)\) ，其中 \(1\le a_i \le 9\) 。对于其中相邻的两项 \(a_i , a_{i + 1}\) ，满足 \(gcd(a_i , a_{i +1})\) 就可以交换，其中 \(1\le i\le n - 1\)
求通过交换可以得到多少种不同的数列
思路
对于 \(1 , 5 , 7\) 这些数可以放到任意位置，放在最后考虑。
对于剩下的 \(2 , 3 , 4 , 5 , 6 , 8 , 9\) ，我们注意到 \(6\) 与其他书的 \(gcd\) 都不为 \(1\) ，所以两个 \(6\) 之间的数一定不会被交换出去。
那么整个数列就可以看成被 \(6\) 分开成了若干块。
把剩下的数分成两组 \(2 , 4 , 8\) 和 \(3 , 9\) 。
两类数都不能与同类交换，也就是确定了相对顺序，二两类数互相可以交换。
设两类数分别有 \(x\) 个和 \(y\) 个。
那么这里的方案数就是 \(C(x + y, x)\) ，因为确定了 \(x\) 的数位置之后， \(y\) 的位置也就确定了。
最后来考虑 \(1 , 5 , 7\)
这些数可以随便放，类似于插板的做法，一种种来处理。
设现在要放的数的数量有 \(x\) 个，已经放了的数有 \(y\) 个。
那么现在的答案就是 \(C(x + y , x)\)
code
#include <bits/stdc++.h>
#define LL long long
#define fu(x , y , z) for(int x = y ; x <= z ; x ++)
#define fd(x , y , z) for(int x = y ; x >= z ; x --)
using namespace std;
const LL mod = 998244353;
const int N = 1e6 + 5;
int a[N] , n;
LL cnt[N] , inv[N] , fac[N] , ans = 1 , sum;
LL C (LL x , LL y) {
return fac[x] * inv[y] % mod * inv[x - y] % mod;
}
LL ksm (LL x , LL y) {
if (!y) return 1;
LL z = ksm (x , y / 2);
z = z * z % mod;
if (y & 1) z = z * x % mod;
return z;
}
int main () {
freopen ("b.in" , "r" , stdin);
freopen ("b.out" , "w" , stdout);
scanf ("%d" , &n);
fu (i , 1 , n) scanf ("%d" , &a[i]);
fac[0] = 1;
fu (i , 1 , n + 1) fac[i] = fac[i - 1] * i % mod;
inv[n + 1] = ksm (fac[n + 1] , mod - 2);
fd (i , n , 0) inv[i] = inv[i + 1] * (i + 1) % mod;
int l = 1 , r = 1;
LL x = 0 , y = 0;
ans = 1;
while (r <= n) {
cnt[a[r]] ++;
if (a[r] == 6 || r == n) {
x = cnt[2] + cnt[4] + cnt[8];
y = cnt[3] + cnt[9];
ans = ans * C (x + y , x) % mod;
cnt[2] = cnt[4] = cnt[8] = cnt[3] = cnt[9] = 0;
l = r + 1;
}
r ++;
}
sum = n - cnt[1] - cnt[5] - cnt[7];
ans = ans * C (sum + cnt[1] , cnt[1]) % mod;
sum += cnt[1];
ans = ans * C (sum + cnt[5] , cnt[5]) % mod;
sum += cnt[5];
ans = ans * C (sum + cnt[7] , cnt[7]) % mod;
sum += cnt[7];
printf ("%lld" , ans);
return 0;
}