useful-codes

手工栈

1
2
3
int siz=40<<20;//40M
__asm__("movl %0,%%esp\n"::"r"((char*)malloc(siz)+siz));//windows用这个
__asm__("movq %0,%%rsp\n"::"r"((char*)malloc(siz)+siz));//linux用这个

记住要 exit(0)

阅读更多

独木桥

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

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

阅读更多

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

阅读更多