solution-code4763

每种食物的生成函数

汉堡: $\begin {split}1+x^2+x^4+\cdots=\frac 1{1-x^2} \end {split}$
可乐: $\begin {split}1+x=\frac{1-x^2}{1-x}\end {split}$
鸡腿: $\begin {split}1+x+x^2=\frac{1-x^3}{1-x} \end {split}$
蜜桃多: $\begin {split}x+x^3+x^5+\cdots=\frac x{1-x^2} \end {split}$
鸡块: $\begin {split}1+x^4+x^8+\cdots=\frac 1{1-x^4} \end {split}$
包子: $\begin {split}1+x+x^2+x^3=\frac{1-x^4}{1-x} \end {split}$
土豆片炒肉: $\begin {split}1+x=\frac{1-x^2}{1-x} \end {split}$
面包: $\begin {split}1+x^3+x^6+\cdots=\frac 1{1-x^3} \end {split}$

乘在一起得到: $\begin {split}f(x)=\frac x{(1-x)^4}=x\cdot (1-x)^{-4} \end {split}$
带入广义二项式定理得 $\begin {split} f(x)=x\cdot \sum_{i=0}^\infty C_{i+3}^i \cdot x^i \end {split}$
当$\begin {split}i=n-1 \end{split}$时第$n-1$项为 $\begin {split} x\cdot C_{n+2}^n \cdot x^n=C_{n+2}^3\cdot x^n\end{split}$
所以答案就为$\begin {split} ans=\frac{n(n+1)(n+2)}6 \end {split}$

阅读更多

[luogu4834]萨塔尼亚的期末考试

,

这里有oeis的解释，但是我看不懂
题目大意：快速地求 $\begin {split} ans=\frac{\sum_{i=1}^n(i\cdot fib(i))}{\frac{n(n+1)}2} \end {split}$ $\begin {split} \because \sum_{i=1}^n fib(i)&=1+fib(1)+fib(2)+\cdots+fib(n)-1 \qquad\qquad\quad [1+(-1)==0] \\ & =(fib(2)+fib(1))+fib(3)+\cdots+fib(n)-1 \qquad [fib(1)==fib(2)] \\ & =(fib(3)+fib(2))+fib(4)+\cdots+fib(n)-1 \qquad [fib(1)+fib(2)==fib(3)] \\ & =\cdots \\ & = fib(n+2)-1 \\ \end {split}$ $\begin {split} \therefore \sum_{i=1}^n i\cdot fib(i)&=n\sum_{i=1}^n fib(i)-\sum_{i=1}^{n-1}\sum_{j=1}^i fib(j) \\ & = n(fib(n+2)-1)-\sum_{i=1}^{n-1}(fib(i+2)-1) \\ & = n\cdot fib(n+2)-n-(\sum_{i=1}^{n-1}fib(i+2))+(n-1) \\ & = n\cdot fib(n+2)-(\sum_{i=1}^{n+1}fib(i)-2)-1 \\ & = n\cdot fib(n+2)-(fib(n+3)-1-2)-1 \\ & = n\cdot fib(n+2)-fib(n+3)+2 \end {split}$
写一个矩阵快速幂就可以解决问题，时间复杂度$\begin {split} O(T\cdot log_2(n))\end {split}$，但是不出意料的T掉了
观察一下结果，可以发现我们分别对ans中两个相邻的fib值进行计算，这并没有利用好矩阵乘法的性质
回想一下最初学习矩阵快速幂的时候，老师演算fib的时候是一个$1\times 2$的矩阵乘上$2\times 2$的矩阵，像这样： $\begin {bmatrix}fib(n)\\fib(n-1)\end {bmatrix} \begin {bmatrix}1&1\\1&0\end {bmatrix}= \begin {bmatrix}fib(n-1)\\fib(n-2)\end {bmatrix}$
我们用老师最初讲的方法来计算fib的值，可以节省一半的时间，在加上$2\times 2$的矩阵乘法不用for循环，就可以轻松切过这道题了～

UPD: 老师最后写的方法并不是错的，在只求一次或者不相邻的项中会显得更快一些，但这并不代表我们可以忘掉原来讲的那种方法（这真的是一道好题）
最终的矩阵为： $\begin {bmatrix}1\\0\end {bmatrix} \begin {bmatrix}1&1\\1&0\end {bmatrix}^{n+3}$

阅读更多

NTT用到的各种素数

,

转载自 miskcoo
是这样的，这几天在写NTT，由于是在模意义下的，需要各种素数……
然后就打了个表方便以后查了
如果$r(2k+1)$是个素数，那么在$\mod r(2k+1)$意义下，可以处理$2k$以内规模的数据，
$2281701377=17\times 227+1$是一个挺好的数，平方刚好不会爆 long long
$1004535809=479\times 221+1$加起来刚好不会爆 int 也不错
还有就是UOJ常用的$998244353=119\times 223+1$
打表方法:对于每个$k$，找到最小r满足$r(2k+1)$是素数（g是$\mod r(2k+1)$的原根）

阅读更多