这场感觉需要记录的东西貌似不是很多，所以写个总的。 B.Boxes 根据贪心原则，其实我们可以注意到两点：1、是否要提示是开始前决定的。要么，你一开始不要提示，全部盒子都开一次。要么，先要提示，根据提示的数量开盒子。因为假若你中途再要提示，可能要到后发现盒子开多了，还不如一开始就要，花费只多不少。2、要了提示后，你一定是按照盒子价值从小到大开的。因为你开一个盒子都是的概率白或黑，因此从总体来说，从小往大开的话，期望的花费会比较少（可以往下看看期望的计算自己思考下）。显然，如果不要提示，则期望为。若要提示，则就要分情况了。因为有了提示，你就知道有几个白几个黑，这时候，你会在中途因为开够数量而停下...

原来上一题是多校第二道期望题啊，我怎么没印象 题目链接：https://ac.nowcoder.com/acm/contest/11166/I 这题转移就比上题容易了些，但这题的状态比较难找到。提取题目中的关键点：p是一个排列，每次选择的数需要大于所有已选的数。因为是一个排列，所以我们可以把当前选的数的大小作为状态。因此，我们可以尝试状态dp[i][j]：上一轮选择了i，前一轮选择了j时的期望轮数。之后，据次得出状态转移式： ps.这里式根据 （可能变成的状态的dp值和+单步贡献）*变成该状态的概率 值得到的。具体看代码吧（） #include <bits/stdc++.h> #d...

链接：https://ac.nowcoder.com/acm/contest/11255/B 这篇题解可能会有些许错误，欢迎大佬们指正Orz 概率生成函数 首先，我们定义概率生成函数(为啥这么定义？菜了，不大清楚，当一个做题方向吧)我们现在需要的出这个函数。 由题意可知：我们抽到的数字的序列，除去最后一个数之外，它肯定是一个不下降的序列，像是1，1，2，3，3，7这样的。这时，我们可以枚举每个数的出现次数，来得到（指的是数字i被抽到的概率）具体的，假如1，1，2，3，3，7这样的序列，对应的就是。我们某个数出现的次数的生成函数，则我们可以知道。根据等比数列求和，因此，记住这个函数，我们后面会用...

所以为什么会在这里出现imo题https://ac.nowcoder.com/acm/contest/11254/E 通过率非常高的一题，然而因为我太菜了，并没有过 这题我认为算是一个套路，实在无法理解可以暂时就留个印象，以后还遇到类似的可以对比着看。这道题一拿到手应该大部分人和我一样想到打表。打出一部分表后，我们发现，任意数都符合条件。 接下来，我们设，则我们固定x，方程可整理为，我们固定x（也就是说我们等会选择枚举x），则，由韦达定理：那么，接下来，我们固定k，我们要计算的是系数为k的(x,y)对数由上面的韦达定理可知：若一对值满足条件，则，另一对符合条件的，系数为k的数对为我们现在知道符...

题目：https://ac.nowcoder.com/acm/contest/11253/J大意为给一个数组a，求数组a中所有大小为k的子集的gcd的乘积。 根据惯例，估计是转化为枚举gcd后统计贡献。对于每个i，我们需要求有几个子集的gcd为i，考虑组合数为，num为数组中i的倍数的个数，但这样统计会包含gcd为i的倍数的集合，因此，考虑从大到小枚举，枚举一个i后，减去gcd为i的倍数的集合的个数，即可得到gcd为i的集合的个数。综上所述，假设gcd为i的集合的个数为，则答案为。但是，还没完，因为数字有这么大，可想而知的值一定不小，因此，考虑欧拉降幂。我们可以先通过扩展欧拉定理求出（或者是）...

题目链接：https://ac.nowcoder.com/acm/contest/11166/G题目大意：给两个数组a,b，现在可以交换a中的数k次，求的最大值。 看了题解。可以这样想：把要求的值看作对每个和前面放符号，满足总的+的数目=总的-的数目。那么，最后的结果就是a、b所有数*符号后的和。统计没有交换前的答案。根据贪心原则，最大的结果应该就是。这样就相当于对每个赋为+，赋为-。考虑交换。显然，我们要交换的目标是两个符号不同的数，然后交换他们的符号，者才能使得答案变化。在考虑贪心，想要最后答案最大，肯定是要使得+的和最大，-的和最小，因此，考虑将上面+的数降序排列为数组add，-的数升序...

题目链接：https://ac.nowcoder.com/acm/contest/11166/H 涉及到的东西其实不是很难，但是多项式加速还是比较难想到的。 题目可以转化为：找到最小的mod，使得$a_i$处于mod的不同同余系中。扫一眼同余的性质，有一条： 若，则。并且，若，则对于p的某一因数，。根据上面两条，我们要求的就是：最小的、且不为所给的数中任意两个数的差的因数的数。但是这个多项式加速就比较难想。我们可以这样总结：若需要对于两个数组中的元素、两两之间进行操作，朴素算法需要，可以考虑多项式优化为。我们可以构造两个多项式：一个多项式系数为表示数i是否出现在数组中。另一个多项式系数表示数-...

A.CCA的词典 没啥好讲的，map记录下出没出现过，然后每次查询枚举下可能的来源，叠加贡献即可。注意特判aa这种情况 map<string,int>cnt; int main(){ int n; cin>>n; for(int i=0;i<n;++i){ string t; cin>>t; cnt[t]++; } int q; read(q); while(q--){ string s; cin>>s; int ans=cnt[s]; if(s.size()==2&&s[0]!=s[1]){ swap(s[0],s[1])...

首先，根据题目要求，因为每一轮都需要把中间给替换掉可知，要想最终钥匙在中间，那么在最后一轮之前钥匙一定不能在中间。又因为一轮可以把中间替换成任意一个非中间元素，再加上经过n轮每轮一共有2种决策，所以共有种局面。所以，得到递推式：。之后，考虑我们要求的答案ans，则有：,要求,考虑求其通项公式，则,代替带入上式： ，这个高中做过不少了吧？得到。这里若不考虑符号，则上下可能都为负数，此时再去+mod之后的结果是上下分别mod之后的结果，不符合题意，因此，我们需要讨论下符号。当n为奇数： n为偶数： 考虑细节：(n为偶数)和(n为奇数)mod 3都为0（打表试试？），所以，3应该放在分子处*3的逆元...

集训营第二次考欧拉降幂了Orz首先不管n，我们就算能选[1,m]的取值的时候的答案。和B题差不多的idea，我们能想到答案其实是,这是一个n+1次的多项式，如果说m很大的话，我们当然不能直接算，但是，我们可以利用拉格朗日插值法求出这个式的值。建议先学习下拉格朗日插值法。之后，考虑的情况，我们当然不能直接算这个m，那么，题目给了模数，我们考虑只求m mod p的值，那么，考虑如何利用f(m mod p)求f(m).因为为n+1次多项式，那么，我们设，则，，二项式定理展开后，发现，因此，我们只需要求。对于,我们考虑欧拉降幂求即可。这道题需要学的主要是欧拉降幂的写法，这里所用的EXP函数的方法，或者...

写给自己：主要要看的是B.F.E.G总结：1.对TSP问题认识不足。2.B题模3这个条件的性质不清楚。3.复数快速幂？不敢往复数想。 注意：为了阅读效果，我把头文件、快读快写删了。需完整代码可以看我提交 A.回文括号序列计数 ll solve(){ if(n==0)return 1; return 0; }C.末三位 直接快速幂 while(~scanf("%d",&n)) printf("%03d\n",ksm(5,n)%1000);D.划数 因为cnt>=11,所以其实是cnt这个数没动过，其他数操作到剩下一个数。特判下n=2。 while(cin>>n>&...

虽然可以找规律，但是太难了Orz蒟蒻只能选择欧拉降幂。我们先来看下扩展欧拉定理：截自oiwiki 欧拉降幂就是用第三条式子来降低幂次，方便计算的。PS：这里为什么不会出现第二条式子的情况？我大概算了下，a取1的情况我们会特判掉，a取2以上大概就不会发现第二条式子的情况了。所以，不需要考虑第二条式子。UPD:保险起见，我还是加了判断是否使用第二条式子的部分。例如，我们按照样例1：我们要求的其实就是： 而如果层数再多:任何数mod 1都为0，直接返回0即可。这可能也是存在规律的依据。大数，写python呀！ from math import log def phi(x): if x == 10: ...

估计多项式会吓到不少人，写个题解装个b。我们数学题嘛，我们把原式写出来：题目要求的就是：设x序列都加u，y序列都加v，则 我们可以令u-v=t,则： 运用初中数学知识，我们我们可以把上式子看作一个二次函数,变量为t。那么，我们就可以知道当u-v取多少的时候，相同x,y下，res能够最小。因此，亮度调整并不是本题的难点所在。但是，题目还允许我们使得x对应的y不一样。观察上式子，我们发现：只有是同时关联x和y的，我们需要求出的是这个式子的最小值。我们可以把这个式子变一下：,这里的x是原来的x反转之后的。我们发现，这是个一个卷积的形式。那么，对于卷积，我们自然想到多项式算法（FFT，NTT），因为没...

看到题目，我想大家第一个想到的就是前缀异或和，因为这种询问一整段的异或和的一半都需要这样处理，不然复杂度太高。之后，题目要询问的就是找到在区间[L,R]中的存在的点sum[l]==sum[r],使得r-l+1最小。若是考虑直接让值对应整个[l,r]区间则会很麻烦，所以，考虑转化为单点维护。考虑单点维护，则有两个选择：要么放在l，要么放在r。那么，我们先试个错误答案，若我们放在r，那么，我们在查询的时候就会遇到麻烦：我们在查询后面的点的时候，我们找不到一个方法确定查询到的值到底是不是属于[L,R]区间的，所以，不能选择r存储。若选择了l，我们就有另一种方法了，那就是离线。我们将询问全部按照r排序...