Megumin's daily record2

由于上一篇记录太长，不方便继续记录以及查看，顺便对前一阶段进行小小的总结，故新开一篇
不知不觉一个月过去了，总的来说这个月进步还是有的，我们顺利拿到了ccpc现场赛的资格，最近的几次训练也基本上能够保持在银左右的水平。但是很显然，问题还是存在的，首先，部分偏简单的题可能还是需要花很久才能解出，但这比以前稍有进步了；其次，付出的努力看不到收获，我相信每个人都在认真做题，可是，要是你努力了，却在训练中得不到体现，这说明了什么呢？每个人分专题练习的意义是在短时间内得到较大的提升，使得每个人都有解决某些较为简单的题的能力，这样可以减轻能切难题的人的负担，留给他们更多的时间去思考难题。

个人总结

• 能够比较熟练的使用FFT,NTT解决一些问题，对这类题的感觉还算不错
• 对线性筛，莫比乌斯反演的理解加深了不少
• 初步掌握了较为简单的博弈问题的解法
• 能够利用dp去求解一些组合问题

努力方向

• 生成函数及多项式运算
• 高斯消元，包括解XOR方程组
• 数位DP
• 面积交

8/23

• 组队练了南阳ccpc，感觉还算可以
• 由于要准备补考，可能最近晚上的时间都不会拿来做题

8/24

• 补了多校的1002,1010,1011
• 小号上紫

8/25

• AC827E Rusty String
• 初步了解FWT
• 整理了杜教求解线性递推数列的模板

8/26

• AC美团CodeM初赛的二分图染色，加深对容斥的理解
• 最近心情很不好加上口腔溃疡，状态极差
• 计划最近做一些比较有难度的组合数学题
• 上bzoj切了两个模板题，结果两个模板都有小问题
  明日目标：
  1.思考OEIS A001499

8/27

• 准备刷bzoj的题了，先从比较水的题开始
  1002 递推+高精度 1026 简单数位DP 1024 DFS 1008 简单组合 2186 线性筛+欧拉函数+扩展欧几里得 4321 DP or 递推
• 补了昨晚AGC的B、vijos上次比赛的博弈和DP
• 4517 组合+错排 2440 乱搞 2761 水 2751 快速幂 2956 分块+前缀和
• 整理了前缀和+分块优化的代码

8/28

• 学习cdq分治，可做题目：hdu5322 hdu5896 bzoj4555 ZOJ3874 Tsinsen A1493 BNUOJ51279 hdu5552
• AC hdu5552 hdu5322 hdu5896
  明日目标：
  1.做完剩下的cdq分治+NTT
  2.做几道莫比乌斯反演的题

8/29

• AC Tsinsen A1493 BNUOJ51279 ZOJ3874 bzoj4555
• 读了几篇论文，初步了解杜教筛

8/30

• 组队练习了2015沈阳现场赛，事实证明暴力还是能出奇迹的，顺便必须要有耐心把所有题读完
• 已了解杜教筛的原理，接下来就是多做题巩固和提供思路，可做题目：BZOJ4805 BZOJ3944 BZOJ3512 BZOJ3930 BZOJ4916 hdu5608 51nod1237
• AC BZOJ4805 BZOJ3944
  明日目标：

1. AC一部分列举的杜教筛的题
2. 阅读杜教筛相关的博客

8/31

• 做了下广西邀请赛的题目
• 晚上去打麻将了

9/1

• AC hdu5608 BZOJ4916

9/2

• 打了下ARC
• 补了昨天div1 B，今天ARC的E
• 最近几天因为要补实习报告，做题的时间要少很多

9/3

• 整理了最大团模板
• AC hdu3585 二分+最大团
• 做了下长沙理工的校赛

9/4

• 整理了杜教筛非map存储的版本，不过需要验证正确性（发现了可能更优的替代办法，unordered_map，（mmp，辣鸡bzoj没法测））
• 1079 dp 2705 欧拉函数 1257 分块+前缀和 2440 莫比乌斯反演+二分 2463 博弈
• AC CF852F
• 晚上的cf做的真烂，明明是能加100分的场，硬是打成了减100分

9/5

• 补了昨晚cf的B,C
• AC LibreOJ β Round #4 求和
• 组队练习，个人贡献出了20+发罚时

9/6

• 补了教育场的F
• 2818 欧拉函数+筛法 2659 找规律 1053 dfs
• 掉下紫名了

9/7

• 补了div1 B,D
• 补了校赛的hgcd，切了几题gcd的水题
• 3884 欧拉定理

9/8

• 划水的一天
• 1951 快速幂+欧拉降幂+lucas+中国剩余定理 1876 大数+gcd 2226 欧拉函数+线性筛

9/9

• AC LibreOJ β Round #4 多项式 广义欧拉定理 Hdu2973 威尔逊定理 hdu4196 快速幂+质因数分解
• AC FZU1054 线性筛+广义欧拉定理+dp FZU1055 约数个数 FZU1056 约数和 FZU1057 矩阵乘法 FZU1058 水 FZU1059 广义欧拉定理
• 学习几个数论定理:威尔逊定理、Pell方程、广义欧拉定理
  明日目标

1. AC hdu2837 hdu3221

9/10

• 又是划水的一天
• hdu283 广义欧拉定理 hdu3221 矩阵快速幂+广义欧拉定理

9/11

• AC CF856C
• 补了沈阳邀请赛的dp
• 4802 Miller_Rabin素数判别+Pollard_Rho大质因数分解
• 整理了Miller_Rabin、Pollard_Rho的模板，可做题目：hdu5391 hdu4910 hdu2138 hdu3864 poj3641 poj1811 CF324 (Div 2)D

9/12

• AC gym101063 K
• 补了17省赛的I，虽然结果式子很简单，看似是个推公式的题，其实结果是由容斥得到的。如果我们对(x_i)不加限制，即其取值为(0)至(P-1)，那么我们很容易可以得到结果为(P^{n-1})。然后我们考虑容斥，我们需要减去一个(x_i)超过其上限的情况，再加上两个(x_i)超过其上限的情况，...，而(n)个(x_i)超过其上限的情况是不存在的，因为(sum_{i}a_i<P)。而容斥的结果可以合并成一个多项式(frac{(P-a_1)*(P-a_2)*...*(P-a_n)-(-a_1)*(-a_2)*...*(-a_n)}{P})。
• 组队练习

9/13

• 划水++
• hdu5391 hdu4910 hdu3864 CF324 (Div 2)D poj3641 poj1811

9/14

• 1192 水 2431 dp+前缀和优化 2299 gcd 1432 找规律 1041 数论 1034 贪心 1406 质因数

9/15

• gym100792H dp+滚动数组+异或性质优化
• 补了新疆网络赛的I
• 2301 莫比乌斯反演+前缀和分块优化 1607 筛法 1485 卡特兰数+分解质因数 4318 dp 2618 半平面交

9/16

• COGS2294 FFT 51nod1172 FFT
• 整理了FFT模任意素数的模板
• AC hdu6088 莫比乌斯反演+FFT 西安网络赛E,F

9/17

• 2005 线性筛+莫比乌斯反演+前缀和分块优化 3142 差分+组合
• 补了网赛的10
• poj1808 平方剩余

9/18

• 补了昨晚div2的ABCD
• 补了2015沈阳的F，K（我要死了）
• AC hdu5525 事实证明分数对非质数取模还是有很多需要注意的地方

9/19

• 补了2017NEERC的H
• 4407 莫比乌斯反演+线性筛+分块前缀和优化 3288 高斯消元+线性筛
• 组队练习

9/20

• 补了cf的ABC
• 基本掌握线性筛，有出一道题的想法，调试完成

9/21

• 3561 莫比乌斯反演+线性筛
• 补了2017NEERC的B

9/22

• hdu4143 枚举因数 hdu5730 cdq分治+fft hdu5734 一元二次方程 hdu5742 水 hdu5744 水
• 3309 莫比乌斯反演+线性筛

9/23

• 北京网络赛
• 晚上老乡聚会