template
**** Combinatorics ****
const ll M = 1e9+7; // default modulus
// --- Basic modular operations ---
ll mod(ll x, ll m = M){
return ((x % m) + m) % m;
}
ll mod_add(ll a, ll b, ll m = M){
return (a + b) % m;
}
ll mod_sub(ll a, ll b, ll m = M){
return ((a - b) % m + m) % m;
}
ll mod_mul(ll a, ll b, ll m = M){
return ((a % m) * (b % m)) % m; // safe for small numbers
}
ll mod_pow(ll a, ll b, ll m = M) {
ll res = 1;
a %= m;
while(b) {
if(b & 1) res = (res * a) % m;
a = (a * a) % m;
b >>= 1;
}
return res;
}
// --- Modular inverse for prime modulus ---
// Fermat's Little Theorem: a^(m-2) ≡ a^(-1) (mod m)
ll mod_inv_prime(ll a, ll m = M){
return mod_pow(a, m - 2, m);
}
// --- Modular inverse for non-prime modulus ---
// Extended Euclidean Algorithm: ax + my = gcd(a, m)
// inverse exists only if gcd(a, m) = 1
ll mod_inv_nonprime(ll a, ll m){
ll m0 = m, x0 = 0, x1 = 1;
if(m == 1) return 0;
while(a > 1){
ll q = a / m;
ll t = m;
m = a % m, a = t;
t = x0;
x0 = x1 - q * x0;
x1 = t;
}
if(x1 < 0) x1 += m0;
return x1;
}
// --- Modular division ---
// Use appropriate inverse function depending on whether m is prime or not
ll mod_div_prime(ll a, ll b, ll m = M){
return mod_mul(a, mod_inv_prime(b, m), m);
}
ll mod_div_nonprime(ll a, ll b, ll m){
return mod_mul(a, mod_inv_nonprime(b, m), m);
}
const int N = 1e6 + 5; // max n
ll fact[N], invfact[N];
// Precompute factorials and inverses (for prime modulus)
void precompute_fact(ll m = M) {
fact[0] = 1;
for(int i = 1; i < N; i++) fact[i] = mod_mul(fact[i-1], i, m);
invfact[N-1] = mod_inv_prime(fact[N-1], m); // inverse of fact[n]
for(int i = N-2; i >= 0; i--) invfact[i] = mod_mul(invfact[i+1], i+1, m);
}
// nCr modulo m (works only for prime m)
ll nCr(ll n, ll r, ll m = M){
if(r < 0 || r > n) return 0;
return mod_mul(fact[n], mod_mul(invfact[r], invfact[n-r], m), m);
}
// nPr modulo m
ll nPr(ll n, ll r, ll m = M){
if(r < 0 || r > n) return 0;
return mod_mul(fact[n], invfact[n-r], m);
}
**** Number theory ****
// GCD
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
// LCM
ll lcm(ll a, ll b) { return a / gcd(a,b) * b; }
// Fast exponentiation
ll power(ll a, ll b, ll m = LLONG_MAX) {
ll res = 1;
a %= m;
while(b) {
if(b & 1) res = (res * a) % m;
a = (a * a) % m;
b >>= 1;
}
return res;
}
// divisors function using √n
vector<int> divisors(int n) {
vector<int> div;
int sq = (int)sqrt(n);
for(int i = 1; i <= sq; i++) {
if(n % i == 0) { // divisible
div.push_back(i);
if(n / i != i) // avoid double-counting the square root
div.push_back(n / i);
}
}
sort(div.begin(), div.end()); // optional: ascending order
return div;
}
// Prime factorization (O(sqrt(n)))
vector<pair<ll,ll>> prime_factors(ll n){
vector<pair<ll,ll>> res;
for(ll i=2; i*i<=n; i++){
if(n % i == 0){
ll cnt = 0;
while(n % i == 0) { n /= i; cnt++; }
res.push_back({i,cnt});
}
}
if(n > 1) res.push_back({n,1});
return res;
}
// Sieve of Eratosthenes (primes up to N)
vector<int> sieve(int n){
vector<int> isPrime(n+1,1);
isPrime[0] = isPrime[1] = 0;
for(int i=2; i*i<=n; i++){
if(isPrime[i]){
for(int j=i*i; j<=n; j+=i) isPrime[j]=0;
}
}
vector<int> primes;
for(int i=2;i<=n;i++) if(isPrime[i]) primes.push_back(i);
return primes;
}
// -------------------- MISCELLANEOUS --------------------
// Extended Euclidean (solve ax + by = gcd(a,b))
ll extended_gcd(ll a, ll b, ll &x, ll &y){
if(b==0){ x=1; y=0; return a; }
ll x1,y1;
ll g = extended_gcd(b, a%b, x1, y1);
x = y1;
y = x1 - (a/b)*y1;
return g;
}
// Euler's Totient Function (O(sqrt(n)))
ll phi(ll n){
ll res = n;
for(ll i=2; i*i<=n; i++){
if(n % i == 0){
while(n % i == 0) n /= i;
res -= res/i;
}
}
if(n > 1) res -= res/n;
return res;
}
// Check if number is prime (O(sqrt(n)))
bool is_prime(ll n){
if(n<2) return false;
for(ll i=2; i*i<=n; i++) if(n%i==0) return false;
return true;
}
**** Bitwise ****
#include<bits/stdc++.h>
using namespace std;
// Checks if kth bit of x is set (1) or not (0)
int check_kth_bit(int x, int k) {
return (x >> k) & 1;
}
// Prints the positions of all set (1) bits in binary representation of x
void print_on_bits(int x) {
for (int k = 0; k < 32; k++) {
if (check_kth_bit(x, k)) {
cout << k << ' '; // prints the position of the set bit
}
}
cout << '\n';
}
// Returns the count of set (1) bits in binary representation of x
int count_on_bits(int x) {
int ans = 0;
for (int k = 0; k < 32; k++) {
if (check_kth_bit(x, k)) {
ans++;
}
}
return ans;
}
// Checks if x is even or odd
bool is_even(int x) {
if (x & 1) {
return false;
}
else {
return true;
}
}
// Sets the kth bit of x to 1 and returns the result
int set_kth_bit(int x, int k) {
return x | (1 << k);
}
// Sets the kth bit of x to 0 and returns the result
int unset_kth_bit(int x, int k) {
return x & (~(1 << k));
}
// Toggles the kth bit of x and returns the result
int toggle_kth_bit(int x, int k) {
return x ^ (1 << k);
}
// Checks if x is a power of 2
bool check_power_of_2(int x) {
return count_on_bits(x) == 1;
}
int count_on_bits_fast(int x) {
return __builtin_popcount(x); // for 32-bit
}
int count_on_bits_fast(ll x) {
return __builtin_popcountll(x); // for 64-bit
}
// Lowest set bit / highest set bit
int lowest_set_bit(int x) { return x & -x; }
int highest_set_bit(int x) { return 31 - __builtin_clz(x); } // position
// Check if exactly one bit is set
bool is_single_bit(int x) { return x && (x & (x-1)) == 0; }
// Mask creation
int mask(int l, int r) { // bits l to r inclusive set to 1
return ((1 << (r-l+1)) - 1) << l;
}
// Subset iteration
for(int sub = mask; sub; sub = (sub-1) & mask) {
// iterate all subsets of mask
}
// Bit parity
int parity(int x) { return __builtin_parity(x); } // 1 if odd number of set bits
Comments
Post a Comment