Fancy's Blog

FFT & NTT

6月 8, 2016

pkusc第一天就有FFT可是我不会做呢 Let's Orz Menci 从多项式乘法到快速傅里叶变换 by Miskcoo（里面有NTT） 1 UOJ #34. 多项式乘法第一行两个整数 \(n\) 和 \(m\) ，分别表示两个多项式的次数。第二行 \(n+1\) 个整数 ...

3月 8, 2016

OI&ACM, 数学

全概率公式: 全期望公式: 1 【bzoj 1076】[SCOI2008]奖励关系统将依次随机抛出k次宝物，每次你都可以选择吃或者不吃（必须在抛出下一个宝物之前做出选择，且现在决定不吃的宝物以后也不能再吃）。宝物一共有n种，系统每次抛出这n种宝物的概率都相同且相互独立。获取第 ...

3月 7, 2016

OI&ACM, 数学

抽屉原理（鸽笼原理）
容斥原理
加法原理
乘法原理
排列 \(A(n,m)=\frac{n!}{(n-m)!}\)
组合 \(C(n,m)=\frac{n!}{m!\times (n-m)!}\)
公式：
\(C(n,m)=C(n,n-m)\)
\(C(n,m)=C(n-1,m)+ C(n-1,m-1)\)
\(C(n,0)+C(n,1)+\dots +C(n,n-1)+C(n,n)=2^n\)
可重复组合方程x1+x2+…+xn=r的非负整数解的个数：
可以理解为，将r个1排成一排，插入n-1个分隔符，把r个1分成n段，n段中的1的个数即是方程的一个解。
插入n-1个分隔符的过程，实际上就是从n+r-1个位置中选择n-1个位置放分隔符，其余r个位置放1，
共有\(C(n+r-1,n-1)=C(n+r-1,r)\)种
Catalan数 \(\frac{C(2n,n)}{n+1}\)
\(C_n^m\)中每个元素出现的次数为\(C_n^m \times m \div n=C(n-1,m-1)\)