855学习记录算法杂谈——炎泽汐$de$ Blog

//快速幂
long long q_poe(long long x, long long n, long long mod){
    long long res = 1;
    while(n > 0){
        if(n & 1) {
            res = (res * x) % m;
        }
        x = (x * x) % m;
        n >>= 1;    //  相当于 n /= 2;
    }
    return res;
}

//慢速乘 
long long s_mul(long long a,long long b,long long mod){
    long long res=0;
    while(b){
        if(b%2){
            res=(res+a)%p;
        }
        a=(a+a)%p;
        b/=2;
    }
    return res;
}

// 矩阵快速幂
typedef vector<int> vec;
typedef vector<vec> mat;
typedef long long ll;
const int M = 1E9;

mat mul(mat &A, mat &B){
    mat C(A.size(), vec(B[0].size()));
    for(int i = 0; i < A.size(); i++){
        for(int k = 0; k < B.size(); k++){
            for(int j = 0; j < B[0].size(); j++){
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % M;
            }
        }
    }
    return C;
}

mat pow(mat A, ll n){
    mat B(A.size(), vec(A.size()));
    for(int i = 0; i < A.size(); i++){
        B[i][i] = 1;
    }
    while(n > 0){
        if(n & 1) {
            B = mul(B, A);
        }
        A = mul(A, A);
        n >>= 1;
    }
    return B;
}

//埃氏筛
int prime[maxn];  //存储素数的数组
bool is_prime[maxn];  //对应位置的数是否为素数

int a_shai(int n){
    int p = 0;
    for(int i = 0; i <= n; ++i){
        is_prime[i] = true;
    }
	
    is_prime[0] = is_prime[1] = false;
    for(int i = 2; i <= n; ++i){
        if(is_prime[i]){
            prime[p++] = i;
            for(int j = i + i; j <= n; j += i){
            	is_prime[j] = false;
            } 
        }
    }
    return p; 
}

//递归 GCD
int gcd(int a, int b){
    return b == 0 ? a : gcd(b, a % b);
}

//快速选择算法 
int quick_sort(int l, int r, int k){
    if(l >= r){
        return nums[k];
    }
	
    int i = l, j = r, x = nums[i + j >> 1];
    
    while(i < j){
        while(nums[i] < x){
            i++;
        }
        
        while(nums[j] > x){
            j--;
        }
        
        if(i < j){
            swap(nums[i], nums[j]);
        }  
    }
	
    if(j >= k){
        return quick_sort(l, j, k);
    }else{
        return quick_sort(j + 1, r, k);
    }
}

//前缀和
pre[0] = nums[0];
for(int i = 1; i < n; i ++){
    pre[i] = pre[i - 1] + nums[i];
}

for(int i = 1; i < nums.Length; i ++){
    for(int j = 1; j < nums[i].Length; j++)  {
        pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + nums[i][j];
    }
}

//差分 
void insert(int l, int r, int c){
    b[l] += c;
    b[r + 1] -= c;
}
for(int i = 1; i <= n; i++){
    insert(i, i, a[i]);
}

void insert(int x1, int y1, int x2, int y2, int c){
    b[x1][y1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y2 + 1] += c;
}

for(int i = 1; i <= n; i++){
    for(int j = 1; j <= m; j++){
        insert(i, j, i, j, a[i][j]);
    }
}

//树状数组 (动态前缀和)
const int N = 100000;
int a[N], tr[N];
int n;

//求末位 0 函数
int lowbit(int x){
    return x & -x;
} 

//添加函数
void add(int x, int v){
    for(int i = x; i <= n; i += lowbit(i)){
        tr[i] += v;
    }
} 

//区间和函数
int query(int x){
    int res = 0;
    for(int i = x; i; i -= lowbit(i)){
        res += tr[i];
    }
} 

//逆序对 
vector<int> tmp;
int count;
void mergeSort(vector<int>& nums, int l, int r) {
    if(l >= r){
        return;
    }
		
    int mid = (r - l) / 2 + l;
    mergeSort(nums, l, mid);
    mergeSort(nums, mid + 1, r);
 
    int i = l, j = mid + 1;
    int cur = 0;
    while(i <= mid && j <= r) {
        if(nums[i] <= nums[j]) {
            tmp[cur++] = nums[i++];
        }else {
            tmp[cur++] = nums[j++];
            count += mid - i + 1;
        }
    }
        
    while (i <= mid) {
        tmp[cur++] = nums[i++];
    }
        
    while (j <= r) {
        tmp[cur++] = nums[j++];
    }

    for (int i = 0; i < r - l + 1; ++i) {
        nums[l+i] = tmp[i];
    }
}

tmp.resize((int)nums.size(), 0);
mergeSort(nums, 0, (int)nums.size() - 1);