Cauphenuny's blog

发表于 更新于 分类于

zxy 讲题的时候顺便讲了一下

min-25 筛可以解决一种函数前缀和，

发表于 更新于 分类于 ， ，

本来是考试的，但是数论忘了，只好滚去学数论。

性质

若 f(x)f(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}

阅读全文 »

发表于 更新于 分类于 ，

总结

Day1

开考先看看三个题，发现 T2 是个构造，T3 不像是会做的题目，然后就开始想第一题。

正好昨天看了一眼 wqs 二分，这个题目也有一个只能选 kk 个的限制，于是思路逐渐跑偏，也把模型转换了一下，大概就花了一两个小时的时间，然后发现我不太会做没有限制 kk 个的情况，但是我还是觉得只是自己最后一步思考得不够深入，画了一堆图，就一直想，甚至把手推 wqs 二分，把昨天没看懂的部分想明白了，最后还是放弃了这个思路，然后很快就想出了一个二分加双指针的做法，也没有什么细节，很快就码完了，但是调了一小会儿，过了几个样例然后就已经十一点半还是十二点了​。

阅读全文 »

发表于 更新于 分类于 ， ， ，

乘法

NTT

构造模意义单位根。

发现 δpgk=(p−1)gcd⁡(k,p−1)\delta_pg^k=\dfrac{(p-1)}{\gcd(k, 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

阅读全文 »

发表于 更新于 分类于 ， ， ，

快速沃尔什变换也许是快速地求位运算卷积的一种方法。

给定序列 AA 和 BB ，求 CC，满足 ci=∑i=j⊕kajbkc_i=\sum\limits_{i=j\oplus k}a_jb_k，其中 ⊕\oplus 是某种运算。

与 FFT 一样， FWT 有几个流程，先将 A,BA,B 变换为 FWT⁡(A),FWT⁡(B)\operatorname{FWT}(A),\operatorname{FWT}(B)，再计算 FWT⁡(C)i=FWT⁡(A)i×FWT⁡(B)i\operatorname{FWT}(C)_i=\operatorname{FWT}(A)_i\times\operatorname{FWT}(B)_i，最后将 FWT⁡(C)\operatorname{FWT}(C) 转换回 CC。

总之，是 O(nlog⁡n)O(n\log n) — O(n)O(n) — O(nlog⁡n)O(n\log n) 的三步。

阅读全文 »

发表于 更新于 分类于 ， ，

改题，然后发现需要填填坑。

其实学起来也没有那么难。