独木桥

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

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

阅读更多

[BZOJ3771]Triple

, ,

不同情况的生成函数

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

阅读更多

[BZOJ3759] Hungergame

,

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

阅读更多

solution-code2593

每种水的生成函数

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

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

阅读更多

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}$

阅读更多