注意：

• 空(逃)

阅读更多

每种食物的生成函数

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

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

阅读更多

模板题，多注意细节即可

阅读更多

转载自byvoid
这道题正确的解法是构造网络，求网络最小费用最大流，但是模型隐藏得较深，不易想到。构造网络是该题的关键，以下面一个例子说明构图的方法和解释。

阅读更多

注意！

• 如果在线段树Build的时候要初始化根节点的值，一定要用fpos！

阅读更多

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

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

阅读更多

转载自 miskcoo
是这样的，这几天在写NTT，由于是在模意义下的，需要各种素数……
然后就打了个表方便以后查了
如果$r(2k+1)$是个素数，那么在$\mathrm{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是$\mathrm{mod}r(2k+1)$的原根）

阅读更多

注意：

• 空

可行性剪枝:

最优性剪枝:

状态压缩:

一个既简单又难写的算法
注意：

• 空

阅读更多

作为压轴题，题目描述很长、很难理解
还没写好 QwQ

阅读更多