nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 多项式多项式在计算机中一般以数组方式储存，假设有一个多项式$f(x)$，并且$x^i$前面的系数为$a_i$，那么显然我们恰好可以用一个数组$a$来描述这个多项式， 多项式的系数$a_i$恰好存...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 1234567891011// a^x === b x=lg(a,b)int bsgs_lg(int a,int b,int mod){ map<int,int&g...

公式

$$
g(1)\sum_{i=1}^nf(i)=\sum_{i=1}^{n}(f*g)(i)-\sum_{d=2}^{n}g(d) \sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}f(i)
$$

使用

很多时候我们会碰到求积性函数前缀和的情况，由于积性函数的前缀和不一定依然是积性函数，所以我们需要使用一些技巧。

比如给你一个积性函数$f(x)$, 现在要求你计算$\begin{aligned}\sum_{i=1}^n f(x)\end{aligned}$。

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 积性函数对于一个离散函数$f(x), x\in Z^+$ , 如果$\forall \gcd(a,b)=1$都有$f(a\cdot b)=f(a)\cdot f(b)$, 则称函...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 很早就想写这个了，觉得好厉害，结果分析停留在理论上，其实时间复杂度贼高 123456789101112131415161718192021222324252627282930313233343536...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 强联通123456789101112131415161718192021222324252627282930313233343536373839404142434445464748struct ...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748struct Gra...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 先bb一堆dij算法很简单，就是通过不断的松弛离源最近的点，说白了，就是一个bfs变种,或者叫做启发式搜索？启发函数就是当前的距离。搜索过程中松弛点 A*算法也不难，本质上就是启发式搜索，核心就...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 让你用lg的时间复杂度求下面这东西(n<1e18) $$\begin{aligned}&\prod_{i=1…n}{(2i-1)} %2^{64}\&suppos...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 大范围贪心，小范围暴力这一类做法，通常不是很好想，但是很多题目都能这样做。 例题有一个超级大的背包，物品的价值等于容量，但是物品只有8种容量分别为1-8 给你每个物品的数量ai，和背包总容量w，...