min-25 筛
zxy 讲题的时候顺便讲了一下
min-25 筛可以解决一种函数前缀和，
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 Cauphenuny's Blog！
相关推荐
2020-12-03
树的重心相关结论
转载：pyqpyq...
2021-05-29
莫比乌斯反演
本来是考试的，但是数论忘了，只好滚去学数论。 性质 若 f(x)f(x)f(x) 和 g(x)g(x)g(x) 均为积性函数，则以下函数也为积性函数： h(x)=f(xp)h(x)=fp(x)h(x)=f(x)g(x)h(x)=∑d∣xf(d)g(xd)\begin{aligned} h(x)&=f(x^p)\\ h(x)&=f^p(x)\\ h(x)&=f(x)g(x)\\ h(x)&=\sum_{d\mid x}f(d)g(\frac{x}{d}) \end{aligned} h(x)h(x)h(x)h(x)=f(xp)=fp(x)=f(x)g(x)=d∣x∑f(d)g(dx) 设 x=∏pikix=\prod p_i^{k_i}x=∏piki 若 F(x)F(x)F(x) 为积性函数，则有 F(x)=∏F(piki)F(x)=\prod F(p_i^{k_i})F(x)=∏F(piki) 。 若 F(x)F(x)F(x) 为完全积性函数，则有 F(X)=∏F(pi)kiF(X)=\prod...
2021-03-23
多项式部分运算
乘法 NTT 构造模意义单位根。 发现 δpgk=(p−1)gcd(k,p−1)\delta_pg^k=\dfrac{(p-1)}{\gcd(k, p -1)}δpgk=gcd(k,p−1)(p−1)，当 n∣(p−1)n|(p-1)n∣(p−1) 时， δpg(p−1)/n=(p−1)gcd(p−1n,p−1)=n\delta_pg^{(p-1)/n}=\dfrac{(p-1)}{\gcd(\frac{p-1}{n}, p-1)}=nδpg(p−1)/n=gcd(np−1,p−1)(p−1)=n 令 ωn=g(p−1)/n\omega_n=g^{(p-1)/n}ωn=g(p−1)/n ，则 ωn0,ωn1,⋯ ,ωnn−1\omega_n^0,\omega_n^1,\cdots,\omega_n^{n-1}ωn0,ωn1,⋯,ωnn−1...
2021-04-17
HNOI2021总结
总结 Day1 开考先看看三个题，发现 T2 是个构造，T3 不像是会做的题目，然后就开始想第一题。 正好昨天看了一眼 wqs 二分，这个题目也有一个只能选 kkk 个的限制，于是思路逐渐跑偏，也把模型转换了一下，大概就花了一两个小时的时间，然后发现我不太会做没有限制 kkk 个的情况，但是我还是觉得只是自己最后一步思考得不够深入，画了一堆图，就一直想，甚至把手推 wqs 二分，把昨天没看懂的部分想明白了，最后还是放弃了这个思路，然后很快就想出了一个二分加双指针的做法，也没有什么细节，很快就码完了，但是调了一小会儿，过了几个样例然后就已经十一点半还是十二点了。 接着赶紧看第二题，没有什么思路，再加上把题目想的复杂了一点，觉得这种限制很难跑，就先写了高斯消元，但是我已经半年没写过高斯消元了，调了一个小时，然后发现这个做法假掉了，赶紧上了一个随机化，在 12:58 的时候过了样例，第三题就没有看。 最终分数：90+0+090+0+090+0+0 ，T1 被卡常了，T2 没搞到分 总结一下 Day1 的失误主要是 T1...
2020-10-03
可持久化平衡树
link fhq 改几个函数就可以了 12345int refresh(int id) { tot++; p[tot] = p[id]; return tot;} 123456789101112131415void split_by_val(int rt, int &a, int &b, int val) { if (rt == 0) { a = b = 0; return; } if (p[rt].val <= val) { a = refresh(rt);// split_by_val(p[rt].rs, p[a].rs, b, val); pushup(a);//记得是pushup(a)，不是pushup(rt)！！！ } else { b = refresh(rt);// split_by_val(p[rt].ls, a,...
2021-02-06
P5851 (USACO19DEC) Greedy Pie Eaters P
区间 dp ，注意枚举端点 i，j，k 的顺序，模拟一下就好了，如果使用了未更新的状态，就是错的 sorry for that i don’t have a chinese input method Functions: g(x, l, r) means we have the largest cow which can eat pos(x) , and it can only affect pies in [l, r] f(x, l, r) means the weight summary that we can get from a sequence of cows, and it only affect pies in [l, r] So we have the things below: 12345678910111213foreach cow_i foreach x in range[l_i, r_i] g(x, l_i, r_i) = w_i;foreach k in [1 -> n] foreach i in [k -> 1], j in [k...
评论