有顺序的树链剖分模板题，注意Node中ans初始值为0（否则相当于空序列中有一种颜色）并且Lval和Rval的值不能存在于序列之中

阅读更多

你在桥上看风景，看风景的人在轰炸机上看着你。

一句话：两个人相遇后可以看做互换身份然后走和没相遇直接穿过去是一样的

阅读更多

由于内容过长、公式较多，暂时将内容隐藏，请公式恐惧症们做好心理准备。

阅读更多

不同情况的生成函数

我们先设$\begin{array}{r}a(x)\end{array}$为丢失一把斧头的生成函数，$\begin{array}{r}b(x)\end{array}$位丢失两把一样的斧头的生成函数，$\begin{array}{r}c(x)\end{array}$位丢失三把一样的斧头的生成函数
对于样例来说： $\begin{array}{rl}a(x)& =x^4+x^5+x^6+x^7\\ b(x)& =x^8+x^{10}+x^{12}+x^{14}\\ c(x)& =x^{12}+x^{15}+x^{18}+x^{21}\end{array}$
再设$\begin{array}{r}A(x)\end{array}$为丢失一把斧头的生成函数，$\begin{array}{r}B(x)\end{array}$位丢失两把不同的斧头的生成函数，$\begin{array}{r}C(x)\end{array}$位丢失三把不同的斧头的生成函数
对于样例来说：$\begin{array}{rl}A(x)& =a(x)\\ B(x)& =a^2(x)-b(x)\\ C(x)& =a^3(x)-3a(x)b(x)+2c(x)\end{array}$
解释一下$\begin{array}{r}C(x)\end{array}$，首先随意的选择三个斧头（可以相同），然后减去选出两把相同的斧头和另一把斧头（也可以相同），但是三个相同的被减了三次，所以要加2
由于数据范围较大，需要用FFT或NTT优化

阅读更多

转载自joyouth
首先我们不难看出如果存在一个异或和为0的子集，那么先手必胜，否则先手必败
证明如下：
1、首先如果至少存在一个异或和为0的子集，那么一定存在一个异或和为0的子集使得选取之后剩下的数的任意子集异或和不为0
2、假设我们已经选取了一个异或和为0的子集，无论后手怎么做，我们总是有办法使得当前选取的子集异或和为0，因为后手无论是拿石子还是取石子之后，当前子集异或和不等于0，根据Nim游戏可知，此时先手一定有方案使得异或和为0
至此，我们证明了如果至少存在一个异或和为0的子集，先手必胜
那么题目就转化为求是否存在一个子集异或和为0，用线性基即可

阅读更多

每种水的生成函数

第1种: $\begin{array}{r}1+x+x^2+\cdots =\frac{1}{1-x}\end{array}$
第2种: $\begin{array}{r}1+x=\frac{1-x^2}{1-x}\end{array}$
第3种: $\begin{array}{r}1+x+x^2+x^3+x^4=\frac{1-x^5}{1-x}\end{array}$
第4种: $\begin{array}{r}1+x^5+x^{10}+\cdots =\frac{1}{1-x^5}\end{array}$
第5种: $\begin{array}{r}1+x^2+x^4+\cdots =\frac{1}{1-x^2}\end{array}$

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

阅读更多

每种食物的生成函数

汉堡: $\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
这道题正确的解法是构造网络，求网络最小费用最大流，但是模型隐藏得较深，不易想到。构造网络是该题的关键，以下面一个例子说明构图的方法和解释。

阅读更多

这里有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}$

阅读更多