Cauphenuny's Blog

众所周知终端中删掉文件之后无法恢复。 解决方案 trash-cli 但这样虽然能够恢复文件，却无法跟 Finder 共用同一个废纸篓。 使用 applescript 传消息给 Finder 123456789101112131415161718192021222324#!/usr/bin/env python3import osimport sysimport subprocessif len(sys.argv) > 1: files = [] for arg in sys.argv[1:]: if os.path.exists(arg): p = os.path.abspath(arg).replace('\\', '\\\\').replace('"', '\\"') files.append('the POSIX file "' + p +...

考前复习

自制长沙话拼音方案

zxy 讲题的时候顺便讲了一下 min-25 筛可以解决一种函数前缀和，

本来是考试的，但是数论忘了，只好滚去学数论。 性质 若 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...

总结 Day1 开考先看看三个题，发现 T2 是个构造，T3 不像是会做的题目，然后就开始想第一题。 正好昨天看了一眼 wqs 二分，这个题目也有一个只能选 kkk 个的限制，于是思路逐渐跑偏，也把模型转换了一下，大概就花了一两个小时的时间，然后发现我不太会做没有限制 kkk 个的情况，但是我还是觉得只是自己最后一步思考得不够深入，画了一堆图，就一直想，甚至把手推 wqs 二分，把昨天没看懂的部分想明白了，最后还是放弃了这个思路，然后很快就想出了一个二分加双指针的做法，也没有什么细节，很快就码完了，但是调了一小会儿，过了几个样例然后就已经十一点半还是十二点了​。 接着赶紧看第二题，没有什么思路，再加上把题目想的复杂了一点，觉得这种限制很难跑，就先写了高斯消元，但是我已经半年没写过高斯消元了，调了一个小时，然后发现这个做法假掉了，赶紧上了一个随机化，在 12:58 的时候过了样例，第三题就没有看。 最终分数：90+0+090+0+090+0+0 ，T1 被卡常了，T2 没搞到分 总结一下 Day1 的失误主要是 T1...

乘法 NTT 构造模意义单位根。 发现 δpgk=(p−1)gcd⁡(k,p−1)\delta_pg^k=\dfrac{(p-1)}{\gcd(k, p -1)}δp​gk=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δp​g(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​...

快速沃尔什变换也许是快速地求位运算卷积的一种方法。 给定序列 AAA 和 BBB ，求 CCC，满足 ci=∑i=j⊕kajbkc_i=\sum\limits_{i=j\oplus k}a_jb_kci​=i=j⊕k∑​aj​bk​，其中 ⊕\oplus⊕ 是某种运算。 与 FFT 一样， FWT 有几个流程，先将 A,BA,BA,B 变换为 FWT⁡(A),FWT⁡(B)\operatorname{FWT}(A),\operatorname{FWT}(B)FWT(A),FWT(B)，再计算 FWT⁡(C)i=FWT⁡(A)i×FWT⁡(B)i\operatorname{FWT}(C)_i=\operatorname{FWT}(A)_i\times\operatorname{FWT}(B)_iFWT(C)i​=FWT(A)i​×FWT(B)i​，最后将 FWT⁡(C)\operatorname{FWT}(C)FWT(C) 转换回 CCC。 总之，是 O(nlog⁡n)O(n\log n)O(nlogn) — O(n)O(n)O(n) — O(nlog⁡n)O(n\log...

改题，然后发现需要填填坑。 其实学起来也没有那么难。

Review 爆炸了，毒瘤出题人一场比赛 3 个数学题 solution 题还没有改完 其实是开学了要补作业