数学&计算几何

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为素数。
逆元可以利用扩展欧几里德或欧拉函数求得：

1. 扩展欧几里德：bx+py=1 有解，x就是所求
2. 费马小定理：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;
}