【题解】ars[A001]相控阵
Link→
模拟赛 T1
一道简单好想小可爱题。
首先我们很容易得到一个结论，就是若想使总作用力最大，那么五个核弹中一定会有四个反应关系去对总作用力产生贡献。
证明的话：
五个核弹相当于一个五元环，不同模式相当于对点进行染色，我们不妨规定两种模式分别染色为红和蓝。
因为边数 \(n\) 为 \(10\) 的倍数，所以我们规定总共有 \(2m\) 个五元环。所以若一个五元环染出 \(2\) 蓝 \(3\) 红，那么必有另一个五元环染成 \(3\) 蓝 \(2\) 红。
如果一个五元环染出 \(1\) 蓝 \(4\) 红，必有另一个是 \(4\) 蓝 \(1\) 红，那么只有其中两条边可以为总作用力产生贡献，必然不优。
若染出 \(5\) 红同理，必有另一个是 \(5\) 蓝，没有边可以贡献，必然不优。
那么我们就知道最大总作用力一定是由每个五元环的其中最大的 \(4\) 条边贡献的。
如果每个五元环选边方案固定，那么总方案数是 \(2m \choose m\) （\(2m\) 个五元环中 \(m\) 个染成 \(2\) 蓝 \(3\) 红，剩下 \(m\) 个染成 \(3\) 蓝 \(2\) 红）
这部分可以用逆元 \(O(n)\) 计算，不再赘述。
那么我们现在就要考虑对于每个五元环，我们有多少种方案。
因为每个五元环要选其中最大的 \(4\) 个边，那么也就意味着，我们一定不选最小的那个边。即最小边的左右点染为同色，若有多个值相等的最小边，则就有多种染色方案。
如图：
故我们将每个五元环内部的方案数乘上五元环染色分配方案数即为最终总方案数。
最后注意模数是 \(998244\) \(\color{red}\large8\) \(53\) 而不是 \(998244353\)
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int _ = 3e5 + 5;
const int mod = 998244853;
int n; int a[_];
int fac[_], inv[_];
int ans = 1;
void init() {
fac[0] = fac[1] = inv[0] = inv[1] = 1;
for(int i = 2; i <= n; ++i) fac[i] = fac[i - 1] * i % mod;
for(int i = 2; i <= n; ++i) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
for(int i = 1; i <= n; ++i) inv[i] = inv[i - 1] * inv[i] % mod;
}
int C(int _n, int _m) {
return fac[_n] * inv[_m] % mod * inv[_n - _m] % mod;
}
signed main() {
ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
cin >> n;
for(int i = 1; i <= n; ++i)
cin >> a[i];
init();
for(int i = 1; i <= n; i += 5) {
sort(a + i, a + i + 5); int cnt = 1;
for(int j = i + 1; j <= i + 4; ++j)
if(a[j] == a[j - 1]) ++cnt;
else break;
ans *= cnt, ans %= mod;
}
ans = ans * C(n / 5, n / 10) % mod;
cout << ans << endl;
return 0;
}
总体来说难度 csp-s 第一题或者更简单，作为签到题很合适！一起来赞美良心出题人吧！