CF 中高难度数学题刷题简记
zhugezy
https://codeforces.com/profile/zhugezy
997C 组合数学，容斥原理瞎搞，公式推导
622F 拉格朗日插值（比较裸）+ 观察优化
734F 位运算定理(fuck())+位运算瞎搞计算(check())
439E 组合数学，容斥简单瞎搞
446C 二次剩余发现性质（5是1e9+9的二次剩余），线段树支持区间加等比数列及区间求和((a_l+=v^1,a_{l+1}+=v^2...))
487C 寒假camp做过的（自己又忘了怎么做了，反省），智商题，构造，注意特判
912E 折半、二分答案、双指针check
258D 简单dp (p_k[i][j])表示(P_k(a_i>a_j)(k)是第(k)次更新后的情况())
959F 线性基裸题，求一个数有多少种子集的xor等于它。
906D 欧拉降幂裸题，注意(Mod(a,b)=a<b?a:a\%b+b).
2019.12.02
266E 线段树维护(i^k*a_i(kleq 5)).弱智题
235E rng_58公式(sum_{i=1}^asum_{j=1}^bsum_{k=1}^cd(ijk)=sumlimits_{gcd(i,j)=gcd(j,k)=gcd(k,i)=1}lfloorfrac{a}{i} floorlfloorfrac{b}{j} floorlfloorfrac{c}{k} floor)，把一个([gcd(i,j)=1])替换成(sum_{d|gcd(i,j)}mu(d)=summu(d)[d|i][d|j])(也可以反演一下),搞一搞得到式子
预处理gcd少一个log，总共是(O(n^2logn))的。
2019.12.03
285E dp +组合数学 关键是搞清每个good position被重复算了多少次。对有(j+m)个good position的一个排列，在计算至少有(j)个good position的情况数(f(j))时被算了(C_{j+m}^m)次。从这(j+m)个position中任意挑出(m)个，都是一个(f(j))的可行情况。
963C 傻逼题 按高度分个类判一判算一算gcd就行了
305D 傻逼题 观察到是在链上建长度为k+1的边
542D (J(x)=prod(p_i^{e_i}+1)),然后爆搜艹过去就行了，反正涉及到这种质因数分解的题很难跑到最坏情况。反正我爆搜没艹过去，最后改了个dp型的写法过了。
2019.12.04
1045D 关键是发现(E(X)=E(v)-E(e)),随便搞一下就过了，我太菜了
1096E 组合数学，学到许多，这次是一个 把n拆分成p个数，使得每个数(leq m)的方案数。这个可以容斥来搞:(sumlimits_{i=0}^p(-1)^iC_p^if(n-i(m+1),p)).明天或者后天写一篇博客自己总结一下TwelveFold Way以及加了各种限制条件的盒子放球/插挡板问题吧。
2019.12.05
643E (dp[v][h])表示v为根的子树高度不超过h的概率。维护(hleq 30)多就能把误差降到(10^{-6}).暴力维护就行。
2019.12.08
747F 求出若干位数有多少种方案，递归乱搞，这么简单的题为啥我没做出来/////
93E 卡常题 爆搜剪枝记忆化 (f(m,n)=sumlimits_{i=1}^n[a_1 ot|i][a_2 ot|i]...[a_m ot|i]=f(m-1,n)-f(m-1,lfloorfrac{n}{a_m} floor))
要把(a)倒序排序，过于傻逼
185D 终于独立写出了一道题，打表找规律，详见博客
2019.12.09
1264C 稍微简单一些，推出dp式子发现可以O(1)维护更新就行了。
665F 同hdu 5901 一个叫lehmer_pi的算法，据说(O(n^{2/3}))求出小于等于n的素数个数。加到板子里了。