Tips
数学&计算几何
PI
const double PI=acos(-1);
圆内接多边形周长
sin函数的使用方法 2*r*sin(PI/n) 表示圆内接多边形的边长
组合数
ll C(ll n, ll m) {//组合数 C(n,m)
if (m < 0) return 0;
if (n < m) return 0;
if (m > n - m) m = n - m;
ll up = 1, down = 1;
for (ll i = 0; i < m; i++) {
up = up * (n - i) % mod;
down = down * (i + 1) % mod;
}
return up * getInv(down) % mod;
} 乘法逆元
这种方法只适用于对答案模一个大质数的情况。
乘法逆元：(a/b)%mod=a*(b^(mod-2)) mod为素数。
逆元可以利用扩展欧几里德或欧拉函数求得：
- 扩展欧几里德：bx+py=1 有解，x就是所求
- 费马小定理：b^(p-1)=1(mod p),故b*b^(p-2)=1(mod p),所以x=b^(p-2)
int inv(int a) {
//return fpow(a, MOD-2, MOD);
return a == 1 ? 1 : (long long)(MOD - MOD / a) * inv(MOD % a) % MOD;
}
LL C(LL n,LL m) {
if(m < 0)return 0;
if(n < m)return 0;
if(m > n-m) m = n-m;
LL up = 1, down = 1;
for(LL i = 0 ; i < m ; i ++){
up = up * (n-i) % MOD;
down = down * (i+1) % MOD;
}
return up * inv(down) % MOD;
} 卢卡斯定理
当n和m比较大，mod是素数且比较小的时候（10^5左右），通过Lucas定理计算
Lucas定理：A、B是非负整数，p是质数。A B写成p进制：A=a[n]a[n-1]…a[0]，B=b[n]b[n-1]…b[0]。
则组合数C(A,B)与C(a[n],b[n])C(a[n-1],b[n-1])…C(a[0],b[0]) mod p同余
即：Lucas(n,m,p)=C(n%p,m%p)Lucas(n/p,m/p,p)
#include<iostream>
using namespace std;
typedef long long ll;
int quick_power_mod(int a,int b,int m){//pow(a,b)%m
int result = 1;
int base = a;
while(b>0){
if(b & 1==1){
result = (result*base) % m;
}
base = (base*base) %m;
b>>=1;
}
return result;
}
//计算组合数取模
ll comp(ll a, ll b, int p) {//composite num C(a,b)%p
if(a < b) return 0;
if(a == b) return 1;
if(b > a - b) b = a - b;
int ans = 1, ca = 1, cb = 1;
for(ll i = 0; i < b; ++i) {
ca = (ca * (a - i))%p;
cb = (cb * (b - i))%p;
}
ans = (ca*quick_power_mod(cb, p - 2, p)) % p;
return ans;
}
ll lucas(ll n, ll m, ll p) {
ll ans = 1;
while(n&&m&&ans) {
ans = (ans*comp(n%p, m%p, p)) % p;//also can be recusive
n /= p;
m /= p;
}
return ans;
}
int main(){
ll m,n;
while(cin>>n>>m){
cout<<lucas(n,m,10007)<<endl;
}
return 0;
} C(n % mod, m % mod) % mod;如果太大还是利用上面的逆元来处理。
半预处理
由于Lucas定理保证了阶乘的数均小于p，所以可以讲所有的阶乘先预处理，优化C（n,m）
mod的要求：p<10^6，且为素数
有效范围：1<=n,m<=10^9
//半预处理
const ll MAXN = 100000;
ll fac[MAXN+100];
void init(int mod) {
fac[0] = 1;
for (int i=1; i<mod; i++){
fac[i] = fac[i-1] * i % mod;
}
}
//半预处理逆元求C（n，m）%mod
ll C(ll n, ll m) {
if ( m>n ) return 0;
return fac[n] * (GetInverse(fac[m]*fac[n-m], mod)) % mod;
} 求一个数的因数
int work(int num) {
int factor[1600], m = 0;
for (int i = 1; i <= num / i; i++) {
if (num % i == 0) {
factor[++m] = i;
if (i != num / i) factor[++m] = num / i;
}
}
return m;
} 分解质因数
const int maxn = 1005;
ll prime_num[maxn], num; //质因数的个数
ll prime[maxn];
ll dp[maxn][maxn];
void divid(ll n){ //分解正整数n
num = 0;
if (n % 2 == 0) {
ll term = 0;
while (n % 2 == 0) {
term++;
n /= 2;
}
prime_num[num] = term;
prime[num++] = 2;
}
for (ll i = 3; i * i <= n; i += 2)
if (n % i == 0) {
ll term = 0;
while (n % i == 0) {
term++;
n /= i;
}
prime_num[num] = term;
prime[num++] = i;
}
if (n > 1) {
prime[num] = n;
prime_num[num++] = 1;
}
} 苹果篮子
const int maxn = 1005;
ll dp[maxn][maxn];//多少种放法
ll f(ll m, ll n){ // m个苹果 n个篮子
dp[0][0] = 1;
for (int i = 1; i <= n; ++i)
for (int j = 0; j <= m; ++j)
if (j >= i) dp[i][j] = (dp[i][j - i] + dp[i - 1][j]) % mod;
else dp[i][j] = dp[j][j];
return dp[n][m];
} STL&编程
cin加速
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
二分
#include <algorithm>
ll a[5] = {-1, 0, 1, 3, 4};
int main() {
bool flag = binary_search(a, a + 5, 6); //有就返回1 没有就返回0
cout << lower_bound(a, a + 5, 0) - a << endl; // 1 返回小于等于0的值的个数
//没找到的的话返回数组末地址
cout << upper_bound(a, a + 5, 0) - a << endl; // 2 返回小于等于0的值的个数
return 0;
} cpp输出小数点后位
cout << fixed << setprecision(p) << ans << endl;
高效的比较函数的写法
inline bool cmps(const int &a, const int &b) { return p[a].y < p[b].y; } scanf整行读入
scanf("%[^\n]%*c",str); //读到'\n'结束读取 read
inline ll read() {
ll s = 0, f = 1;
char ch;
do {
ch = getchar();
if (ch == '-') f = -1;
} while (ch < 48 || ch > 57);
while (ch >= 48 && ch <= 57)
s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
return s * f;
} qkpow/matpow
ll qkpow(ll a, ll b) {
ll ans = 1;
while (b) {
if (b & 1) ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
ll getInv(ll a) { return qkpow(a, mod - 2); } //求一个数的逆元 #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
struct node { //矩阵类
ll matrix[2][2];
node() { memset(matrix, 0, sizeof(matrix)); } //初始化
void one() {
matrix[0][0] = 1;
matrix[1][1] = 1;
} //单位矩阵E
node operator*(node other) { //对*重载 定义矩阵乘法
node ans; //记录乘积
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
for (int k = 0; k < 2; k++) {
ans.matrix[i][j] += matrix[i][k] * other.matrix[k][j];
ans.matrix[i][j] %= mod;
}
return ans;
}
};
node power(node a, ll b) { //快速幂 矩阵a的b次方
node res;
res.one(); //单位矩阵
while (b) {
if (b & 1) res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
int main() {
node temp;
temp.matrix[0][0] = 3;
temp.matrix[0][1] = 1;
temp.matrix[1][0] = 1;
temp.matrix[1][1] = 3;
ll n, flag = 0;
while (cin >> n)
cout << power(temp, n).matrix[0][0] << endl;
return 0;
} vector
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int main() {
vector<int>a;//创建了一个int类型的容器
vector<int>b(5);//创建了一个含有五个元素的int类型的容器
vector<int>c(5,0); //这五个元素的值为0
int b1[]= {1,2,3,4,5};
vector<int>b2(b1,b1+4);//不包括第五个元素
int x;
for(int i=0; i<5; i++) {
cin>>x;
a.push_back(x);
}//逐个输入
a.pop_back();//删除最后一个元素
int len=a.size();//得到元素个数
sort(a.begin(),a.end());
int *p=find(a.begin(),a.end(),3); //查找值为3的元素 返回迭代器 和string的不一样 string的返回下标
a.swap(b);//ab元素整体交换 感觉没必要 直接swap(a,b)不就好了吗
a.insert(a.begin()+1,5); //在a的第1个元素（从第0个算起）的位置插入数值5，如a为1,2,3,4，插入元素后为1,5,2,3,4
a.insert(a.begin()+1,3,5); //在a的第1个元素（从第0个算起）的位置插入3个数，其值都为5
a.insert(a.begin()+1,b+3,b+6);
//b为数组，在a的第1个元素（从第0个算起）的位置插入b的第3个元素到第5个元素（不包括b+6）
//如b为1,2,3,4,5,9,8，插入元素后为1,4,5,9,2,3,4,5,9,8
a.resize(10); //将a的现有元素个数调至10个，多则删，少则补，其值随机
a.resize(10,2); //将a的现有元素个数调至10个，多则删，少则补，其值为2
//遍历 和数组一样用下标遍历比用迭代器遍历要快
//迭代器的本质类似指针
vector<int>::iterator it;//声明一个迭代器，来访问vector容器，作用：遍历或者指向vector容器的元素
for(it=a.begin(); it!=a.end(); it++) {
cout<<*it<<" ";
}
vector<vector<int>>aa(5,vector<int>6);//五行六列的二位数组
bool flag=a.empty(); //是否为空
v.insert(lower_bound(v.begin(), v.end(), a[i]), a[i]);//维护一个有序数组并且插在前面
a.clear();//清除
return 0;
} 算法竞赛之路 文章被收录于专栏
整理、记录算法竞赛的好题
