FFT & NTT

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

概率期望

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

组合数学

  1. 抽屉原理(鸽笼原理)
  2. 容斥原理
  3. 加法原理
  4. 乘法原理
  5. 排列 \(A(n,m)=\frac{n!}{(n-m)!}\)
  6. 组合 \(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\)
  7. 可重复组合 方程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)\)
  8. Catalan数 \(\frac{C(2n,n)}{n+1}\)
  9. \(C_n^m\)中每个元素出现的次数为\(C_n^m \times m \div n=C(n-1,m-1)\)

计算几何

1 【cogs 896】圈奶牛 给出点的坐标,计算最短的能够围住这些点的围栏的长度。 裸凸包 #include<algorithm>#include<cstdio>#include<cmath> using namespace std;int ...

高斯消元

1 【bzoj 1013】[JSOI2008]球形空间产生器sphere 已知一个n维球体的球面上n+1个点的坐标,求球心坐标 手推公式 设球心坐标x01,x02...x0n (xi1-x01)2+(xi2-x02)2+...+(xin-x0n)^2 对于1<=i< ...

数论

看了一天vfk的PPT 1 【bzoj 2186】[Sdoi2008]沙拉公主的困惑 1~N!中与M!互质的数 \(ans=\varphi(m!)\times \frac {n!}{m!} \mod R\) 因为所有小于m!且与m!互质的数加上m!的整数倍都与m!互质,而其他 ...

openjudge小学奥数

1.7647 余数相同问题 已知三个正整数 a,b,c ( <=1000000 )。 现有一个大于1的整数x,将其作为除数分别除a,b,c,得到的余数相同。 请问满足上述条件的x的最小值是多少? 数据保证x有解。 不小心写了个暴力 本来是这样想的: ∵ a ≡ b ...