NOIP2023模拟9联测30 B. 华二
文章目录
- NOIP2023模拟9联测30 B. 华二
- 题目大意
- 思路
- code
题目大意
有一个数列 A = ( a 1 , ⋯ , a n ) A = (a_1 ,\cdots ,a_n) A=(a1,⋯,an) ,其中 1 ≤ a i ≤ 9 1\le a_i \le 9 1≤ai≤9 。对于其中相邻的两项 a i , a i + 1 a_i , a_{i + 1} ai,ai+1 ,满足 g c d ( a i , a i + 1 ) gcd(a_i , a_{i +1}) gcd(ai,ai+1) 就可以交换,其中 1 ≤ i ≤ n − 1 1\le i\le n - 1 1≤i≤n−1
求通过交换可以得到多少种不同的数列
思路
对于 1 , 5 , 7 1 , 5 , 7 1,5,7 这些数可以放到任意位置,放在最后考虑。
对于剩下的 2 , 3 , 4 , 5 , 6 , 8 , 9 2 , 3 , 4 , 5 , 6 , 8 , 9 2,3,4,5,6,8,9 ,我们注意到 6 6 6 与其他书的 g c d gcd gcd 都不为 1 1 1 ,所以两个 6 6 6 之间的数一定不会被交换出去。
那么整个数列就可以看成被 6 6 6 分开成了若干块。
把剩下的数分成两组 2 , 4 , 8 2 , 4 , 8 2,4,8 和 3 , 9 3 , 9 3,9 。
两类数都不能与同类交换,也就是确定了相对顺序,二两类数互相可以交换。
设两类数分别有 x x x 个和 y y y 个。
那么这里的方案数就是 C ( x + y , x ) C(x + y, x) C(x+y,x) ,因为确定了 x x x 的数位置之后, y y y 的位置也就确定了。
最后来考虑 1 , 5 , 7 1 , 5 , 7 1,5,7
这些数可以随便放,类似于插板的做法,一种种来处理。
设现在要放的数的数量有 x x x 个,已经放了的数有 y y y 个。
那么现在的答案就是 C ( x + y , x ) C(x + y , x) 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;
}