( ext{Some Theorems})
Newton二项式定理
((a+b)^n=sumlimits_{i=0}^n{nchoose i}x^iy^{n-i})
Newton多项式定理
((sumlimits_{i=1}^n x_i)^k=sumlimits_{sumlimits_{i=1}^na_i=k}frac{k!}{prodlimits_{i=1}^na_i!}prodlimits_{i=1}^nx_i^{a_i})
Generalized Newton二项式定理
((x+y)^{alpha}=sumlimits_{k=0}^{+infty}{alphachoose k}x^{alpha-k}y^k)
其中({alphachoose k}=frac{alpha^{underline k}}{k!})。
鸽巢原理/抽屉原理
(n)只鸽子住在(m)个巢中，至少有一个巢住着至少(lceilfrac nm ceil)只鸽子。
容斥原理
(|igcuplimits_{i=1}^nA_i|=sumlimits_{m=1}^n(-1)^{m-1}sumlimits_{1le a_1<cdots<a_mle n}|igcaplimits_{i=1}^m A_{a_i}|)
(|igcaplimits_{i=1}^noverline{A_i}|=|U|-|igcuplimits_{i=1}^nA_i|)
Generalized容斥原理
令(alpha(m)=egin{cases}sumlimits_{|S|=m}|igcaplimits_{xin S}A_x|&m
e0\|U|&m=0end{cases})，(eta(m)=egin{cases}sumlimits_{|S|=m}|(igcaplimits_{xin S}A_x)cap(igcaplimits_{xinoverline S}overline{A_x)}|&m
e0\|igcaplimits_{i=1}^noverline{A_i}|&m=0end{cases})，
则有(eta(m)=sumlimits_{k=m}^n(-1)^{k-m}{kchoose m}alpha(k))。
( ext{Some Algorithms})
Euclid-like算法
下面的除法都表示整除
令(g(a,b,c)=frac{ax+b}c)，求(f(r,t,a,b,c,n)=sumlimits_{x=0}^nx^rg(a,b,c)^t)。
Part.1
(age cvee bge c)
(f(r,t,a,b,c,n)=sumlimits_{x=0}^nx^r[frac acx+frac bc+g(amod c,bmod c,c)]^t)
把后面的用Newton二项式定理展开再展开。
(f(r,t,a,b,c,n)=sumlimits_{i=0}^t{tchoose i}(frac ac)^isumlimits_{j=0}^{t-i}{t-ichoose j}(frac bc)^jf(r+i,t-i-j,amod c,bmod c,c,n))
Part.2
(a=0vee t=0vee an+b<c)
自然数幂和。
Part.3
(a<cwedge b<cwedge t e0wedge an+b>c)
我们知道有(x^a=sumlimits_{i=0}^{x-1}((i+1)^a-i^a))。
令(m=frac{an+b}c>0)，那么有
(f(r,t,a,b,c,n)=sumlimits_{x=0}^nx^rsumlimits_{y=0}^m[frac{ax+b}c>y]((y+1)^t-y^t))
(f(r,t,a,b,c,n)=sumlimits_{y=0}^{m-1}((y+1)^t-y^t)sumlimits_{x=0}^n[frac{cy+c-b-1}a<x]x^r)
把后面的部分容斥一下，记(S_x(n)=sumlimits_{i=0}^ni^x)
(f(r,t,a,b,c,n)=m^tS_r(n)-sumlimits_{y=0}^{m-1}((y+1)^t-y^t)S_r(frac{cy+c-b-1}a))
把((y+1)^t)用Newton二项式定理展开
(f(r,t,a,b,c,n)=m^tS_r(n)-sumlimits_{i=0}^{t-1}{tchoose i}sumlimits_{y=0}^{m-1}y^iS_r(frac{cy+c-b-1}a))
前面可以插值算，我们考虑一下后面的部分。
众所周知(S_p(x))是一个(a+1)次多项式。
设(S_p(x)=sumlimits_{i=0}^{p+1}s_{p,i}x^i)。(a)直接Bernoulli数代进去就行了。
这样原式的后面一坨就是
(sumlimits_{i=0}^{t-1}{tchoose i}sumlimits_{y=0}^{m-1}y^isumlimits_{x=0}^{r+1}s_{r,x}(frac{cy+c-b-1}a)^x=sumlimits_{i=0}^{t-1}{tchoose i}sumlimits_{j=0}^{r+1}s_{r,j}sumlimits_{x=0}^{m-i}x^i(frac{cx+c-b-1}a)^j=sumlimits_{i=0}^{t-1}{tchoose i}sumlimits_{j=0}^{r+1}s_{r,j}f(i,j,c,c-b-1,a,m-1))
也就是说(f(r,t,a,b,c,n)=m^tS_r(n)-sumlimits_{i=0}^{t-1}{tchoose i}sumlimits_{j=0}^{r+1}s_{r,j}f(i,j,c,c-b-1,a,m-1))。
所以我们需要对于每个((a,b,c,n))处理出所有(i+jle r+t)的(f(i,j,a,b,c,n))。
直接做是(O((r+t)^4log n))的，同时需要(O((r+t)^2log n))的空间。
用栈模拟递归同时加滚动数组可以做到(O((r+t)^2))的空间。
Part.3部分的式子可以考虑先枚举(i)，对每一组((r,j))，计算出(sumlimits_{j=0}^{r+1}s_{r,j}f(i,j,c,c-b-1,a,m-1))。然后转移时先枚举((r,t))，再枚举每一组(i)算贡献。
Part.1部分的式子可以通过分步操作，即一次(a
ightarrow amod c)一次(b
ightarrow bmod c)来做到每次只有一个(sum)。
这样可以让时间复杂度做到(O((r+t)^3log n))。
万能Euclid
给定群(<G,+>)以及(g(0),g(1))，定义一个操作序列({a_n}(a_iin{0,1}))的权值为(sumlimits_{i=1}^ng(a_i))。
保证满足(g(S+T)=g(S)+g(T))。（这里的(0,1,S,T)指的都是操作序列）
给定(a,b,cinmathbb N)，线段(y=frac{ax+c}b(xin(0,n]))对应一个操作序列，生成方法如下：
从左往右沿着线段走，并依次进行如下判定：
(1.)若直线与(y=c(cinmathbb N))相交，则往操作序列末尾添加一个(1)操作。
(2.)若直线与(x=c(cinmathbb N))相交，则往操作序列末尾添加一个(0)操作。
求该线段对应的操作序列的权值。
我们将上述问题的答案记为(f(a,b,c,n,p,q))，其中(p=g(0),q=g(1))。
( ext{Part.1})
首先特判(n=0)以及(a=0)的情况。
( ext{Part.2})
我们可以令(cleftarrow cmod b)，这不会产生任何影响，于是我们保证了(c<b)。
( ext{Part.3})
先考虑(age b)的情况。
设(k=lfloorfrac ab
floor)，那么我们可以将函数表示为(y=kx+frac{(amod b)x+c}b)。
这个函数的操作序列相比于(y=frac{(amod b)x+c}b)的唯一区别，是每次添加(0)操作之前，会先添加(k)个(1)操作。
也就是说此时(f(a,b,c,n,p,q)=f(amod b,b,c,n,k*q+p,q))。
( ext{Part.4})
然后考虑(a<b)的情况。
设(k=lfloor y|_{x=n}
floor=lfloorfrac{an+c}b
floor)，如果(k=0)那么(f(a,b,c,n,p,q)=n*p)。
否则先处理(yin(1,k])的部分，考虑以当前将原点改为((0,1))并将坐标翻转，那么这里对应的线段就是(y=frac{bx+(b-c)}a(xin(0,k-1]))。
但是这里的答案并不是(f(b,a,b-c,k-1,q,p))，因为交换(p,q)之后，优先级就被打乱了。
所以我们将线段整体下移(frac1a)，这样就能保证原本的优先级了，答案为(f(b,a,b-c-1,k-1,q,p))。
然后我们考虑(yin(frac cb,1])的部分。
这里(1)操作只会在最后被添加一次，而在这之前会添加(lfloorfrac{b-c}a
floor)个(0)操作。
有一个问题是如果((frac{b-c}a,1))是整点的话，那么这里的(1)操作应该在(0)操作之前。
但是我们注意在(yin(1,k])的计算部分是将翻转后的直线向下平移了(frac1a)的，因此(x=frac{b-c}a)会在(yin(1,k])部分被计算。
也就是说这一部分的答案为(lfloorfrac{b-c-1}a
floor*p+q)。
同理可以得到(yin(k,frac{an+c}b])部分的答案为((n-frac{kb-c-1}a)*p)。
总而言之，此时(f(a,b,c,n,p,q)=lfloorfrac{b-c-1}a
floor*p+q+f(b,a,b-c-1,k-1,q,p)+(n-frac{kb-c-1}a)*p)。
设群(<G,+>)的加法的时间复杂度为(O(t))，那么总体时间复杂度为(O(tlog n))，与Euclid算法类似。