本人太菜了,不是很懂这个东西,只是有点懂了快速傅里叶变换的一种方法,本文没有代码,只是证明了这种快速傅里叶变换的方法是正确的。 本文大量使用复数,i表示$\sqrt{-1}$。 多项式乘法 快速傅里叶变换用于快速解决多项式乘法的问题。即 设$A(x)=\displaystyle\sum_{j=0}^ …
BZOJ2115 Xor

题目大意 给定一张n个点,m条边的无向图,边上有权。 定义一条路径的权值为这条路径上所有边权的异或和。 求一条1到n的路径,可以经过重复的边和点,使得这条路径的权值最大。输出最大的权值。 Solution 由于权值是异或和,所以把一条路径重复经过两次是没有意义的。贡献答案的,只有图中的一些简单环和一 …

题目传送门 只要知道NIM游戏是什么,就会发现这道题其实就是要求n个数异或和为0的方案数,其中这n个数能且只能取小于等于m的质数。 构造向量a[i]=[i为质数],将n个a做异或卷积得到的向量b,b[0]即为答案。 所以只要快速幂求异或卷积就行了。要注意的是,快速幂中求异或卷积的时候不用每次都FWT …

题目大意 你被要求设计一个计算器完成以下三项任务: 给定y,z,p,计算Y^Z Mod P 的值; 给定y,z,p,计算满足xy≡ z ( mod P )的最小非负整数; 给定y,z,p,计算满足y^x ≡ z ( mod P)的最小非负整数。 对于100%的数据,1<=y,z,p<=1 …

题目大意 有多组询问,每次询问$ (\sum_{i=1}^{N!} [gcd(i,M!)==1] )%R$ M<=N<=10,000,000 Solution 本来觉得需要各种反演,但发现只要用好$ \varphi$函数就可以。 一个显然的结论,如果$ gcd(x,M!)=1$,则$ g …

题目大意 设d(x)为x的约数个数。有多组询问,每次给定N、M,求$ \sum_{i=1}^{N}\sum_{i=1}^{m}d(i,j)$ Solution 有一个式子:$ d(n,m)=\sum_{i|n}\sum_{j|m}\varepsilon(gcd(i,j))$。可以自己证明一下。 设n …

题目大意 对于给出的n个询问,每次求$ \sum_{i=a}^{b}\sum_{j=c}^{d}[\gcd(i,j)==k]$。 Solution 如果令f(n,m)=$ \sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)==k]$, 则最后的答案ans=f(b,d)-f( …