标签为 [数学] 的文章

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 ......

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) ......