nagisa_菜鸡

题解

/ 注册

全部文章 / 题解（共9篇）

2021牛客暑期多校训练营10 Game of Death（子集反演（容斥原理）+多项式优化）

链接：https://ac.nowcoder.com/acm/contest/11261/G 确实想不到这个状态设计（），估计是对于子集容斥（反演）这个概念接触不多。。我们设的状态是表示被杀的人刚好是集合S，根据各种反演的惯例我们设表示被杀的人是S的子集，这里，我们子集反演因为根据子集反演(其实就...

数学概率论数论

2021-08-17

3 920

2021牛客暑期多校训练营4 B-Sample Game（概率生成函数、数学推导/期望dp）

链接：https://ac.nowcoder.com/acm/contest/11255/B 这篇题解可能会有些许错误，欢迎大佬们指正Orz 概率生成函数首先，我们定义概率生成函数(为啥这么定义？菜了，不大清楚，当一个做题方向吧)我们现在需要的出这个函数。由题意可知：我们抽到的数字的序列，除去最...

数论多项式

2021-07-27

11 1185

2021牛客暑期多校训练营3 E.Math 解题报告（结论、打表）

所以为什么会在这里出现imo题https://ac.nowcoder.com/acm/contest/11254/E 通过率非常高的一题，然而因为我太菜了，并没有过这题我认为算是一个套路，实在无法理解可以暂时就留个印象，以后还遇到类似的可以对比着看。这道题一拿到手应该大部分人和我一样想到打表。打出...

数论

2021-07-25

5 1394

2021牛客暑期多校训练营2-J.Product of GCDs（扩展欧拉定理+pr分解质因数+容斥原理）

题目：https://ac.nowcoder.com/acm/contest/11253/J大意为给一个数组a，求数组a中所有大小为k的子集的gcd的乘积。根据惯例，估计是转化为枚举gcd后统计贡献。对于每个i，我们需要求有几个子集的gcd为i，考虑组合数为，num为数组中i的倍数的个数，但这样统...

数论

2021-07-20

4 1285

2021牛客寒假算法基础集训营5 C.比武招亲（下）(拉格朗日插值法+欧拉降幂)

集训营第二次考欧拉降幂了Orz首先不管n，我们就算能选[1,m]的取值的时候的答案。和B题差不多的idea，我们能想到答案其实是,这是一个n+1次的多项式，如果说m很大的话，我们当然不能直接算，但是，我们可以利用拉格朗日插值法求出这个式的值。建议先学习下拉格朗日插值法。之后，考虑的情况，我们当然不能...

多项式数论

2021-02-27

0 801

2021寒假算法基础集训营6（A.C.D.水 I.BFSJ.MST B.F.推式子 E.dp G.dp(TSP)/贪心）

写给自己：主要要看的是B.F.E.G总结：1.对TSP问题认识不足。2.B题模3这个条件的性质不清楚。3.复数快速幂？不敢往复数想。注意：为了阅读效果，我把头文件、快读快写删了。需完整代码可以看我提交 A.回文括号序列计数 ll solve(){ if(n==0)return 1; ...

数论贪心 dp

2021-02-26

0 657

【2021牛客寒假算法基础集训营1】H 幂塔个位数的计算（欧拉降幂）

虽然可以找规律，但是太难了Orz蒟蒻只能选择欧拉降幂。我们先来看下扩展欧拉定理：截自oiwiki 欧拉降幂就是用第三条式子来降低幂次，方便计算的。PS：这里为什么不会出现第二条式子的情况？我大概算了下，a取1的情况我们会特判掉，a取2以上大概就不会发现第二条式子的情况了。所以，不需要考虑第二条式子。...

数论

2021-02-04

4 989

Forsaken喜欢数论解题报告(素数筛求最小值因子)

这道题需要了解素数筛的原理，而不是只是套模板。需要明白一点，我们在欧拉筛中筛掉合数用的是这个合数的最小值因子。还记得那一步if(i%primes[j]==0) break;吗？这一步就保证我们用的是最小值因子筛掉所有的合数。我们可以这么理解，当i%primes[j]的时候，i=k*primes[j]...

每日一题数论

2020-06-23

1 659

牛客算法周周练4 C.分解质因数+二分查找

这道题比赛的时候没有写出来。。没有写出来是想不出如何验证这个数是不是符合题目要求的，写不出check函数。参考大佬博客：https://blog.nowcoder.net/n/aa5ff9efa80440c897a9aaae4401a467卡住我的两个点：1、怎么分解出p的因数可以通过一个for和w...

二分数论

2020-04-29

0 673