Skip to content

Common sense

  • 1e9+7

    A large prime, usually used as the modulo.

  • 0x3f3f3f3f

    usually used as +inf int .

    // binary search
int l = 0, r = 0x3f3f3f3f;

// dp memset
memset(dp, 0x3f, sizeof(dp));

  • leetcode errors

    • Index out of bounds

      AddressSanitizer: heap-buffer-overflow 
AddressSanitizer: stack-buffer-overflow
AddressSanitizer: global-buffer-overflow

    • access a deleted array

      AddressSanitizer: heap-use-after-free

  • c++ solution template

    #include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <climits>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <list>
#include <cassert>
#include <unordered_map>

#define DEBUG false

#define $(x) {if (DEBUG) {cout << __LINE__ << ": "; {x} cout << endl;}}
#define _(x) {cout << #x << " = " << x << " ";}

const double E = 1e-8;
const double PI = acos(-1);

using namespace std;

int main() {
    ios::sync_with_stdio(false);

}

  • fast power

    // pow(n, p) % M, p >= 0

// int / long long version
int power_modulo(int n, int p, int M) {
    int res = 1;
    while (p > 0) {
        if (p % 2 == 1) res = (res * n) % M;
        p /= 2;
        n = (n * n) % M;
    }
    return res;
}

// double version
double power(double n, long long p) {
    double res = 1;
    while (p > 0) {
        if (p % 2 == 1) ans *= n;
        p /= 2;
        n *= n;
    }
    return res;
}

  • Fibonacci

    // dynamic programming, O(N)
int fib(int n) {
    if (n == 0) return 0;
    else if (n == 1) return 1;
    int a = 0, b = 1, c;
    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return c;
}

// fast power, O(logN)
int fib(int n) {
    if (n <= 1) return 1;
    vector<vector<int>> a = {{1, 1}, {1, 0}};
    a = matpow(a, n - 2);
    return a[0][0] + a[0][1];
}

vector<vector<int>> matpow(vector<vector<int>> a, int p) {
    vector<vector<int>> ans = {{1, 0}, {0, 1}}; // I
    while (p) {
        if (p % 2) ans = matmul(ans, a);
        p /= 2;
        a = matmul(a, a);
    }
    return ans;
}

vector<vector<int>> matmul(vector<vector<int>> a, vector<vector<int>> b) {
  vector<vector<int>> res(2, vector<int>(2, 0));
  res[0][0] = a[0][0] * b[0][0] + a[0][1] * b[1][0];
      res[0][1] = a[0][0] * b[0][1] + a[0][1] * b[1][1];
      res[1][0] = a[1][0] * b[0][0] + a[1][1] * b[1][0];
  res[1][1] = a[1][0] * b[0][1] + a[1][1] * b[1][1];
    return res;
}

// Binet formula, O(1)
int fib(int n) {
    double r = (1 + sqrt(5)) / 2; // 0.618
    int ans = (int)round(pow(r, n) / sqrt(5)); // rounded results!
    return ans;
}

  • Bit operator

    #define GET_BIT(n, i) (((n) & (1LL << ((i)-1))) >> ((i)-1)) // i start from 1
#define SET_BIT(n, i) ((n) | (1LL << ((i)-1)))
#define CLR_BIT(n, i) ((n) & ~(1LL << ((i)-1)))


// 2's complement
// method1: 全部取反，最后加一 
// e.g., -x == (~x) + 1;
// method2: 从低位开始找到第一个1为止保持不变（包含第一个1），其余取反。
// e.g., 00111100 --> 11000100 (== 11000011 + 1)

// lowbit operator (find the last bit's position)
// lowbit(01101000) --> 00001000
auto lowbit = [](int x) { return x & (-x); }

// highbit (application of lowbit)
// highbit(01101000) --> 01000000
int highbit(int x) {
    int res = 0;
    // delayed update, when i == 0, res == last i.
    for (int i = x; i != 0; i -= lowbit(i)) res = i;
    return res;
}

// application: complement without leading 0
// 00000101 --> 00000010
// this equals to masked complement, where we need a highbit mask, and find out a second-highbit mask is also OK (since the highest bit is always 1)
// 11111010 & 00000111 == 11111010 & 00000011 == 00000010
int maskedComplement(int x) {
    int mask = highbit(x) - 1;
    return (~x) & mask;
}

// display in binary
#include <bitset>
void show_binary(unsigned long long x) {
  printf("%s\n", bitset<64>(x).to_string().c_str());
}

// interesting results
('a' | ' ') == 'a';
('A' | ' ') == 'a';
('b' & '_') == 'B';
('B' & '_') == 'B';
('d' ^ ' ') == 'D';
('D' ^ ' ') == 'd';

// eliminate last 1 in binary format
n = n & (n - 1);

// application
bool isPowerOfTwo(int n) {
    if (n <= 0) return false;
    return (n & (n - 1)) == 0;
}
int count1(int n) {
    int ans = 0;
    while (n) {
        n &= n - 1;
        ans++;
    }
    return ans;
}

// 只出现一次的元素
int singleNumber(vector<int>& nums) {
    int res = 0;
    for (int n : nums) {
        res ^= n;
    }
    return res;
}

// simulate a + b
int add(int a, int b) {
    while (b) {
        unsigned int c = (unsigned int)(a & b) << 1; // to handle negatives
        a ^= b;
        b = c;
    }
    return a;
}

  • implement square root

    // binary search
// O(logx)
float mysqrt(float x， float eps=1e-4) {
    float l = 0, r = x;
    while (r - l >= eps) {
        float m = (l + r) / 2;
        if (m * m - x > eps) r = m;
        else l = m;
    }
    return l;
}

// babylonian method (a special case of Newton's method for finding root)
// O(logx)
float mysqrt(float x, float eps=1e-4) {
    float r = x, r2;
    while (true) {
        r2 = (r + x / r) / 2; // iterate to get better optimzation.
        if (abs(r2 - r) < eps) break; // the thresold.
        else r = r2;
    }
    return r2;
}

  • GCD/LCM

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

int lcm(int a, int b) {
    if (gcd(a,b)>0) {
        return (a / gcd(a, b)) * b;
    }
    return 0;
}

  • is prime

    bool is_prime(int n) {
    if (n <= 1) return false;
    if (n == 2) return true;
    for (int i = 2; i < sqrt(n) + 1; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

// A prime number greater than 3 can be written in the form 6n - 1 or 6n + 1 
// This is of the order O(sqrt(n))  with reduced leading constant
bool is_prime(int n) {
    if (n == 1 || n % 2 == 0) return false;  
    if (n == 2 || n == 3) return true;
    int t = sqrt(n);
    int k = t / 6;
    for (int i = 1; i <= k; i++) {
      if((n%(6*t - 1)==0) || (n%(6*t + 1)==0)) return false;
    }
    return true;
}

// prime table
int is_prime[UP_LIMIT + 1];
for (int i = 1; i <= UP_LIMIT; i++) // init to 1
    is_prime[i] = 1;
for (int i = 4; i <= UP_LIMIT; i += 2) // even number is not
    is_prime[i] = 0;
for (int k = 3; k*k <= UP_LIMIT; k++) // start from 9, end at sqrt
    if (is_prime[k])
        for(int i = k*k; i <= UP_LIMIT; i += 2*k) // every two is not 
            is_prime[i] = 0;

  • combination & permutation number

    乘法逆元

    //// n choose r mod p

// fastpower
using ll = long long;
ll fastpower(ll a,ll b,ll p) {
    ll res=1;
    while(b) {
        if(b&1) res=res*a%p;
        a=a*a%p;
        b>>=1;
    }
    return res;
}

// suitable case: 1 <= r <= n <= 10^3
// 利用递推公式：C(n, r) = C(n-1, r-1) + C(n-r, r)

// suitable case: 1 <= r <= n <= 10^6
// 利用乘法逆元，a^{-1} = a^{p-2} (mod p), 通过nCr = n! / r! / (n-r)!计算，通常用打表的形式。
const int maxn = 1e5+5;
const int p = 1e9+7;

ll fac[maxn], invfac[maxn]; // always use ll, only cast to int for answer.

void init(int n) {
  for (int i = 1; i < n; i++) {
      fac[i] = (ll) fac[i-1] * i % p;
      invfac[i] = (ll) invfac[i-1] * fastpower(i, p-2, p) % p; // O(logn)

  }    
}

ll C(int a, int b) {
    if (a < b) return 0;
    return fac[a] * invfac[b] % p * invfac[a-b] % p;
}


// suitable case: 1 <= r <= n <= 10^18, 1 <= p <= 10^5，p为素数。
// 利用Lucas定理：C(n, r) % p = C(n / p, r / p) * C(n % p, r % p) % p
// 10^18输入范围无法打表，故动态计算逆元
ll C(ll a, ll b, ll p) {
    if (b > a) return 0;
    ll x = 1, y = 1;
    for(int i = 1, j = a; i <= b; i++,j--) {
        x = x * j % p;
        y = y * i % p;
    }
    return x * fastpower(y, p-2, p) % p;
}

ll lucas(ll a, ll b, ll p)
{
    if (a < p && b < p) return C(a, b, p);
    else return C(a % p,b % p, p) * lucas(a/p, b/p, p) % p;
}
    树的拓扑排序数量
    class Solution {
public:
    const int M = 1e9 + 7;
    const static int maxn = 1e5 + 5;
    using ll = long long;
    ll fac[maxn], invfac[maxn];
    vector<vector<int>> children;    

    ll fastpower(ll a,ll b,ll p) {
        ll res=1;
        while(b) {
            if(b&1) res=res*a%p;
            a=a*a%p;
            b>>=1;
        }
        return res;
    }

    void init(int N) {
        fac[0] = invfac[0] = 1;
        for (int i = 1; i < N; i++) {
            fac[i] = (ll) fac[i-1] * i % M;
            invfac[i] = (ll) invfac[i-1] * fastpower(i, M-2, M) % M;
        }
    }

    tuple<int,int> solve(int idx) {
        // leaf
        if (children[idx].empty()) return {1, 1};
        // loop children
        ll res = 1;
        int sum_len = 0;
        for (int i = 0; i < children[idx].size(); i++) {
            auto [len, perm] = solve(children[idx][i]);
            sum_len += len;
            res = res * perm % M * invfac[len] % M;
        }
        res = res * fac[sum_len] % M;
        return {sum_len + 1, res};
    }

    int waysToBuildRooms(vector<int>& prevRoom) {
        // init (note TLE if init 1e5+5)
        init(prevRoom.size() + 5);
        // build tree
        children.resize(prevRoom.size());
        for (int i = 1; i < prevRoom.size(); i++) {
            children[prevRoom[i]].push_back(i);
        }
        // recursive call
        auto [len, ans] = solve(0);
        return ans;
    }
};