首页 > 其他分享 >【题解】ars[A001]相控阵

【题解】ars[A001]相控阵

时间:2023-05-14 11:34:39浏览次数:51  
标签:方案 ars int 题解 作用力 A001 2m fac 五元

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 第一题或者更简单,作为签到题很合适!一起来赞美良心出题人吧!

标签:方案,ars,int,题解,作用力,A001,2m,fac,五元
From: https://www.cnblogs.com/agrumestly/p/17398958.html

相关文章

  • P8430 题解
    前言题目传送门!更好的阅读体验?比较妙的交互题。思路题意就是每次可以询问\([l,r]\)的括号子序列是否为合法,\((n-1)\)次询问后,需要求出整个括号序列。括号序列,自然想到栈。考虑每次进行一个\([\text{top},i]\)的询问。如果是合法,那么\(a_{\text{top}}=\text{LEFT},a......
  • CF543D 题解
    前言题目传送门!更好的阅读体验?比较有趣的换根DP。思路FirstDFS按照换根DP套路,先钦定\(1\)为首都(即根节点),并计算。显然是树形DP。设\(dp_{u}\)表示以\(u\)为根的子树全部满足的方案数。对于一条树边\((u,v)\):如果\((u,v)\)修,就意味着\(v\)对应子树的所......
  • ABC254F 题解
    前言题目传送门!更好的阅读体验?这题trick就是更相减损术:\(\gcd\{a_1,a_2,a_3,\cdots,a_n\}=\gcd\{a_1,a_2-a_1,a_3-a_2,\cdots,a_n-a_{n-1}\}\)。思路有了这个trick之后这题就好做了。并不需要其他题解一样画表格,化简式子就行,过程并没有难点。\[\begin{a......
  • 基于二阶自抗扰ADRC的轨迹跟踪控制,对车辆的不确定性和外界干扰具有一定抗干扰性,基于ca
    基于二阶自抗扰ADRC的轨迹跟踪控制,对车辆的不确定性和外界干扰具有一定抗干扰性,基于carsim和simulink仿真跟踪轨迹为双移线,效果良好,有对应复现资料,是学习自抗扰技术快速入门很好的资料能帮助你节约大量的时间。仿真包运行ID:18112692525521944......
  • 基于滑膜控制的后轮主动(ARS)和DYC的协调稳定性控制,上层ARS产生期望后轮转角度,DYC产生横
    基于滑膜控制的后轮主动(ARS)和DYC的协调稳定性控制,上层ARS产生期望后轮转角度,DYC产生横摆力矩Mz,下层采用基于附着系数和车速对附加横摆力矩进行分配,控制效果良好,能实现车辆在高低附着系数路面下的稳定性,可应用在高速下高低附着系数路面下的轨迹跟踪的横向稳定性控制住。资料中有参......
  • 基于轨迹预测的驾驶员方向控制方法实现的单点预瞄,通过carsim与simulink仿真发现,该方法
    基于轨迹预测的驾驶员方向控制方法实现的单点预瞄,通过carsim与simulink仿真发现,该方法能够良好的实现车俩的轨迹跟踪控制。有对应信息和文件说明。ID:23100684398458311......
  • 基于滑膜控制的后轮主动(ARS)和DYC的协调稳定性控制,上层ARS产生期望后轮转角度,DYC产生横
    基于滑膜控制的后轮主动(ARS)和DYC的协调稳定性控制,上层ARS产生期望后轮转角度,DYC产生横摆力矩Mz,下层采用基于附着系数和车速对附加横摆力矩进行分配,控制效果良好,能实现车辆在高低附着系数路面下的稳定性,后续可应用在高速下高低附着系数路面下的轨迹跟踪的横向稳性。资料中包含对应......
  • UVA12096 题解
    这道题虽然被评黄,但个人感觉不止普及组难度,而且是一道很有价值的题目。题解区里全是\(O(n^2logn)\)的STL大法,我来发一篇\(O(n^2)\)哈希做法。目前0ms喜提最优解。这道题是codeforcesgym的题目,本质上就是模拟栈中集合插入,复制,相加,取交集,取并集的过程。注意,这些集合都是......
  • [AGC001E] BBQ Hard题解
    Problem[AGC001E]BBQHard计算:\[\sum_{i=1}^{n}\sum_{j=i+1}^n\binom{a_i+b_i+a_j+b_j}{a_i+a_j}\]其中\(n\leq2\times10^5\),\(a_i,b_i\leq2000\)Solution以\(a_i\)代\(a_i+b_i\)则等价于求\[\sum_{i=1}^{n}\sum_{j=i+1}^n\binom{a_i+a_j}{b_i+b_j}......
  • 【题解】Luogu[P3750] [六省联考 2017] 分手是祝愿
    Link→小清新dp题,纪念自己的700ac(一个点只有两个状态开和不开,且按两下相当于没按,我们可以从大到小有亮的就按一下,如果我们按到了不需要按的键,就需要再按一下使他变回来。设\(f_i\)表示\(i\)个正确选择变为\(i-1\)个的期望操作次数。则有\(\dfrac{i}{n}\)概率按到......