分类: [数学]

浅谈快速傅里叶变换

本人太菜了,不是很懂这个东西,只是有点懂了快速傅里叶变换的一种方法,本文没有代码,只是证明了这种快速傅里叶变换的方法是正确的。 本文大量使用复数,i表示$\sqrt{-1}$。 多项式乘法 快速傅里叶变换用于快速解决多项式乘法的问题。即 设$A(x)=\displaystyle\sum_{j=0}^{n-1}a_jx^j$ $B(x)=\displaystyle\sum_{j=0}^{m-1}b_jx^j$ 令$C(x)=A(x)\times B(x)$ 则C(x)可表示为: $\displaystyle\sum_{j=0}^{n+m-2}c_jx^j$ 我们要解决的问题是已知a数组和b数组,求c数组。 举个例子:有多项式$A(x)=6x^3+7x^2-10x+9,B(x)=-2x^3+4x-5 ......

BZOJ2115 Xor

题目大意 给定一张n个点,m条边的无向图,边上有权。 定义一条路径的权值为这条路径上所有边权的异或和。 求一条1到n的路径,可以经过重复的边和点,使得这条路径的权值最大。输出最大的权值。 Solution 由于权值是异或和,所以把一条路径重复经过两次是没有意义的。贡献答案的,只有图中的一些简单环和一条1到n的路径。 我们可以事先选出一条1到n的路径(任意),记为“主路径”。假设我们沿着这条路径由1走到n,并得到了这条路径的权值,记为ans。 再将所有环的异或和求出来。最后的答案就是在选取一些环的异或和和ans的异或和的最 ......

BZOJ4589 Hard Nim

题目传送门 只要知道NIM游戏是什么,就会发现这道题其实就是要求n个数异或和为0的方案数,其中这n个数能且只能取小于等于m的质数。 构造向量a[i]=[i为质数],将n个a做异或卷积得到的向量b,b[0]即为答案。 所以只要快速幂求异或卷积就行了。要注意的是,快速幂中求异或卷积的时候不用每次都FWT和UFWT,这样是两个log的,会TLE(观察代码会发现每次UFWT后就会紧接着做一次FWT……没有任何意义)。其实只要FWT一次,对a的每一位都求快速幂就行了,最后再UFWT。   code #include<cstdio& ......

BZOJ2242 计算器

题目大意 你被要求设计一个计算器完成以下三项任务: 给定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<=10^9,为质数,1<=T<=10。 Solution 典型的NOIP三合一题,硬是把三道题合在了一起…… 前两问就不说了(一个快速幂,一个exgcd)…… 而要怎么解决第三问呢? 要用到BSGS(Baby-Step-Giant-Step)算法。用某方姓大佬的话: 就是枚举到根号的暴力 设x=im-j $ y^x=y^{im-j}\equiv z(mod p)$即$ y^{i ......

BZOJ2186 沙拉公主的困惑

题目大意 有多组询问,每次询问$ (\sum_{i=1}^{N!} [gcd(i,M!)==1] )%R$ M<=N<=10,000,000 Solution 本来觉得需要各种反演,但发现只要用好$ \varphi$函数就可以。 一个显然的结论,如果$ gcd(x,M!)=1$,则$ gcd(x+k(M!),M!)=1(k\in\mathbb{N})$ 而因为N!是M!的倍数,所以答案就变成了 $$(\sum_{i=1}^{M!}[gcd(i,M!)==1])(N!/M!)$$ $$=\varphi(M!)(N!/M!)$$ $$=M!\prod_{(p|M!)\land(p\in prime)}(p-1)/p(N!/M!)$$ $$=N!\prod_{(p|M!)\land(p\in prime)}(p-1)/p$$ 所以只要预处理出每个M以内的素数及其逆元,还有每个数的阶乘 ......

BZOJ3994 约数个数和

题目大意 设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<m,然后就可以转化式子了。$$\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{u|i}\sum_{v|j}\varepsilon(gcd(u,v))$$ $$=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{u|i}\sum_{v|j}\sum_{(d|u)\land(d|v)}\mu(d)$$ $$=\sum_{d=1}^{n}\mu(d)\sum_{u=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{v=1}^{\lfloor\frac{m}{d}\rfloor}\lfloor\frac{n}{d ......

BZOJ2301 Problem b

题目大意 对于给出的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(a-1,d)-f(b,c-1)+f(a-1,b-1)。所以只要求f(n,m)。 令$ n1=\lfloor\frac{n}{k}\rfloor$,$ m1=\lfloor\frac{m}{k}\rfloor$;且设n<=m $$f(n,m)=\sum_{i=1}^{n1}\sum_{j=1}^{m1}\varepsilon(gcd(i,j))$$ $$=\sum_{i=1}^{n1}\sum_{j=1}^{m1}\mu(gcd(i,j))*\mathrm{1}$$ $$=\sum_{i=1}^{n1}\sum_{j=1}^{m1}\sum_{(d|i)\land(d|j)}\mu(d)$$ $$=\s ......

BZOJ2440 完全平方数(二分+容斥原理)

题目大意 有几组询问,每次询问第k大的不是完全平方数(1外的)倍数的数。 k<=1000,000,000 Solution 如果可以快速计算1~n区间内不是完全平方数的倍数的个数,这个答案就可以二分了。 令$ x0=ax^2$(x$ \in$ 质数,$ a\in\mathbb{N}$),将n减去x0的个数后发现,所有完全平方数倍数的数都被减去了,而有些这样的数被减了两次。 令$ x0=ax^2$(x=pq p$ \in质数 q \in$质数,$ a\in\mathbb{N}$),x0在上面被减了两次,再把它们加上。 …… 其实就是做容斥。 若x分解质因数后次数都是一,x有偶数个质因数,答案加上$ \frac{n}{x^2}$ 若x分 ......

BZOJ5020在美妙的数学王国中畅游

题目传送门 Solution 在每次询问的x是固定时,可以用LCT维护出一条链上的所有函数的和。而x不固定,该怎么办呢? 其实可以用泰勒展开表示一个函数在某个点上的值。即:$f(x)=\sum_{k=0}^{n}\frac{f^{(k)}(x0)}{k!}(x-x0)^k+\frac{f^{(n+1)}(\xi)}{(n+1)!}{(x-x0)}^{n+1}$ 其中,x0是任意取的一个数,而后面的余项是用来估计误差值的,因为只能计算前面的式子,当余项很小的时候,这个误差就会变小。当n>=15时,这个误差值会小于$1e-7$。 对于具体的这些函数: $f^{(0)}(x)=\sin(ax+b)$, $f^{(k)}(x)=-f^{(k-2)}(x)*a^2$ $f^{(0) ......

BZOJ 3561 DZY Loves Math VI

题目传送门 Solution 很明显是莫比乌斯反演啦 令p=gcd(i,j),且n<m $$=\sum_{i=1}^{n}\sum_{j=1}^{m}{(\frac{i}{p})}^p{(\frac{j}{p})}^{p}{p}^{p}$$ $$=\sum_{p=1}^{n}\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{p}\rfloor}{(ijp)}^p\cdot\varepsilon(gcd(i,j))$$ $$=\sum_{p=1}^{n}p^p\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{p}\rfloor}{(ij)}^p\cdot\mu(gcd(i,j))\ast\mathrm{1}$$ $$=\sum_{p=1}^{n}p^p\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor\fra ......