(mu*I=epsilon)
(sum_{d|x}mu(d)=epsilon)
([gcd(x,y)==1]=sum_{d|x,d|y}mu(d))
(f=g*1\,\,\,\,\,\,g=f*mu)
DFT只能是2的幂次
循环卷积:a(n)卷b(n),NTT开到n,那么自动%n(n是2的幂次)。
bluestein可做非2的幂次
树形dp卡空间:滚动数组,树剖先走重儿子
在模p意义下有
((x+1)^p≡(x^p+1)~mod~p)
[(x+1)^m=(x+1)^{lfloorfrac m p
floor imes p} imes(x+1)^{m~mod~p}
]
[(x+1)^m=(x^p+1)^{lfloorfrac m p
floor} imes(x+1)^{m~mod~p}
]
二项式展开,得:
[sum_{i=0}^m{mchoose i}x^i=sum_{i=0}^{lfloorfrac m p
floor}{lfloorfrac m p
floorchoose i}x^{i imes p} imessum_{i=0}^{m~mod~p}{m~mod~pchoose i}x^i
]
当左边(i)取(n),右边也使(x)指数也取(n)得:
[{mchoose n}={lfloorfrac m p
floorchoose lfloor frac n p
floor} imes {m~mod~pchoose n~mod~p}
]
(lfloor frac n p floor imes p+(n~mod~p)=n)