hard-level-math.cpp

// 🔸 1. Advanced Number Theory ⭐⭐⭐
// Euler’s Totient Function (φ(n)) ⭐⭐⭐
// Euler’s Theorem
// Chinese Remainder Theorem ⭐⭐⭐
// Wilson’s Theorem
// 🔸 2. Advanced Modular Arithmetic
// Modular exponentiation with large numbers
// Lucas Theorem ⭐⭐⭐
// Fast nCr for large N
// 🔸 3. Advanced Combinatorics ⭐⭐⭐
// Stars and Bars ⭐⭐⭐
// Catalan Numbers ⭐⭐⭐
// Derangements
// 🔸 4. Matrix Exponentiation ⭐⭐⭐
// Solve recurrence relations
// Fibonacci in log N
// 🔸 5. Probability & Expected Value ⭐⭐⭐
// Basic probability in CP
// Expected value problems
// 🔸 6. Game Theory ⭐⭐⭐
// Grundy numbers
// Nim Game
// 🔸 7. Advanced Techniques
// FFT (Fast Fourier Transform) ⭐⭐⭐
// Polynomial multiplication






// ⭐ 1.1 Euler’s Totient Function φ(n)
// 💡 Concept

// φ(n) = count numbers from 1..n that are coprime with n.
// Example:
// φ(9)=6
// because {1,2,4,5,7,8} are coprime with 9.

// ⚙️ Formula
// For prime factors:
// φ(n) = n * (p1-1)/p1 * (p2-1)/p2 * ... * (pk-1)/pk
//φ(n)=n * Πp|n(1 - 1/p) for all distinct prime factors p of n

// Where p1, p2, ..., pk are the distinct prime factors of n.
// 🧠 Usage
// Count coprime pairs
// RSA encryption
// ⚙️ Algorithm
// Factor n to find distinct primes
// Apply the formula
// Time complexity: O(√n) for factorization, O(k) for applying formula
// Example: φ(10)
// Prime factors: 2, 5
// φ(10) = 10 * (1 - 1/2) * (1 - 1/5) = 10 * (1/2) * (4/5) = 4
// So φ(10) = 4
// Note: For multiple queries, precompute φ(n) for all n up to a limit using a sieve-like method in O(n log log n).
// Example: Precompute φ(n) for n = 1 to 10
// φ(1) = 1
// φ(2) = 1
// φ(3) = 2
// φ(4) = 2
// φ(5) = 4
// φ(6) = 2
// φ(7) = 6
// φ(8) = 4
// φ(9) = 6
// φ(10) = 4
// This matches our earlier calculation for φ(10) = 4
// 🧠 CP Usage
// Euler theorem
// modular inverse
// coprime count
// graph gcd problems





#include<bits/stdc++.h>
using namespace std;
long long phi(int n){
    long long res=n;
    for(long long 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;
}
int main(){
    int n;
    cin>>n;
    cout<<phi(n)<<endl;
    return 0;
}







// ⭐ 1.2 Euler’s Theorem
// 💡 Formula
// If gcd(a,n)=1:
// a^φ(n) ≡ 1 (mod n)
// Where φ(n) is Euler’s Totient Function.
// 🧠 Use
// Used when modulus is not prime.
// This is generalized Fermat's Little Theorem.
// Example: Compute 3^4 mod 10
// φ(10) = 4 (from previous example)
// Since gcd(3,10)=1, we can use Euler's theorem:
// 3^4 ≡ 1 (mod 10)
// So 3^4 mod 10 = 1
// 🧠 CP Usage
// Modular exponentiation with non-prime moduli
// Modular inverses when modulus is not prime
// Example: Compute modular inverse of 3 mod 10
// Since gcd(3,10)=1, we can use Euler's theorem:
// 3^φ(10) ≡ 1 (mod 10)
// 3^4 ≡ 1 (mod 10)
// To find the modular inverse of 3 mod 10, we can compute 3^(φ(10)-1) mod 10:
// 3^(4-1) ≡ 3^3 ≡ 7 (mod 10)
// So the modular inverse of 3 mod 10 is 7, since (3 * 7) mod 10 = 1
// Note: For large n, precompute φ(n) for all n up to a limit using a sieve-like method in O(n log log n) to efficiently apply Euler's theorem for multiple queries.
// Example: Precompute φ(n) for n = 1 to 10
// φ(1) = 1
// φ(2) = 1
// φ(3) = 2
// φ(4) = 2
// φ(5) = 4
// φ(6) = 2
// φ(7) = 6
// φ(8) = 4
// φ(9) = 6
// φ(10) = 4



#include<bits/stdc++.h>
using namespace std;
long long eulerPhi(int n){
    long long res=n;
    for(long long 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;
}
long long modExp(long long a, long long b, int mod) {
    long long res = 1;
    a = a % mod; // Handle cases where a >= mod
    while(b > 0) {
        if(b & 1) res = (res * a) % mod; // If b is odd, multiply a with result
        a = (a * a) % mod; // Square a
        b >>= 1; // Right shift b (divide by 2)
    }
    return res;
}
int main(){
    int n, a, b, mod;
    cout << "Enter n for φ(n): ";
    cin >> n;
    cout << "φ(" << n << ") = " << eulerPhi(n) << endl;
    cout << "Enter base, exponent and modulus for modular exponentiation: ";
    cin >> a >> b >> mod;
    cout << a << " raised to the power " << b << " modulo " << mod << " is: " << modExp(a, b, mod) << endl;
    return 0;
}





// 🔶 1) COPRIME COUNT ⭐⭐⭐
// 💡 What is Coprime?

// Two numbers are coprime if:
// gcd(a,b)=1

// Example:

// gcd(8,15)=1

// So 8 and 15 are coprime.

// 🎯 Problem Type

// Count how many numbers from 1..n are coprime with n.

// This is exactly:

// ✅ Euler Totient Function
// // φ(n) = count of numbers from 1..n that are coprime with n.
//formula: φ(n) = n * Πp|n(1 - 1/p) for all distinct prime factors p of n
// 🧠 INTUITION

// Suppose n = 12

// Numbers from 1..12:

// 1 2 3 4 5 6 7 8 9 10 11 12

// Check gcd with 12:

// gcd(1,12)=1 ✅
// gcd(5,12)=1 ✅
// gcd(7,12)=1 ✅
// gcd(11,12)=1 ✅
// So answer = 4

// Thus:

// φ(12)=4
// ⚙️ ALGORITHM
// Prime factorize n.
// For every unique prime p:
// result -= result / p





// 🔶 2) GRAPH GCD PROBLEMS ⭐⭐⭐

// This is a very important advanced pattern.

// 💡 CORE IDEA

// Graph nodes contain values.

// We use GCD relation between connected nodes.

// Usually questions ask:

// path gcd
// gcd of subtree
// maximum gcd path
// count edges where gcd > 1
// graph connectivity using gcd
// 🎯 TYPE A: CONNECT IF GCD > 1

// Very famous OA problem.

// 🧪 Example

// Array:

// [6,10,15,7]

// Make edge if gcd > 1

// Connections
// gcd(6,10)=2 ✅
// gcd(6,15)=3 ✅
// gcd(10,15)=5 ✅
// gcd(7, others)=1 ❌

// Graph:

// 6 --- 10
//  \   /
//   15

// 7 isolated
// 🧠 QUESTION

// How many connected components?

// Answer:

// 2
// ⚙️ BRUTE FORCE ALGORITHM
// Try all pairs
// If gcd > 1 connect
// DFS/BFS components


#include<bits/stdc++.h>
using namespace std;
int countComponents(vector<int>& a){
    int n=a.size();
    vector<vector<int>> adj(n);

    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            if(__gcd(a[i],a[j])>1){
                adj[i].push_back(j);
                adj[j].push_back(i);
            }
        }
    }

    vector<int> vis(n,0);

    function<void(int)> dfs = [&](int u){
        vis[u]=1;
        for(int v:adj[u]){
            if(!vis[v]) dfs(v);
        }
    };

    int comp=0;
    for(int i=0;i<n;i++){
        if(!vis[i]){
            comp++;
            dfs(i);
        }
    }

    return comp;
}
int main(){
    int n;
    cout<<"Enter number of elements: ";
    cin>>n;
    vector<int> a(n);
    cout<<"Enter the elements: ";
    for(int i=0;i<n;i++) cin>>a[i];
    cout<<"Number of connected components: "<<countComponents(a)<<endl;
    return 0;
}







// ⭐ 1.3 Chinese Remainder Theorem ⭐⭐⭐
// 💡 Problem Type

// Solve:

// x % 3 = 2
// x % 5 = 3
// x % 7 = 2
// 🧠 Usage
// multiple modular constraints
// cyclic schedules
// clock problems
// distributed hashing
//formula: x = a1*M1*y1 + a2*M2*y2 + ... + ak*Mk*yk where Mi = M/mi and yi is the modular inverse of Mi mod mi
// where M = m1*m2*...*mk
// where mi are the moduli and ai are the remainders
//
// ⚙️ Algorithm
// Extended Euclidean Algorithm to find inverses
// Combine equations iteratively
// Time complexity: O(k^2) for k equations
// Example: Solve x % 3 = 2, x % 5 = 3, x % 7 = 2
// Step 1: Calculate M = 3*5*7 = 105
// Step 2: Calculate Mi = M/mi
// M1 = 105/3 = 35
// M2 = 105/5 = 21
// M3 = 105/7 = 15
// Step 3: Calculate yi such that Mi*yi ≡ 1 (mod mi
// y1: 35*y1 ≡ 1 (mod 3) → y1 = 2
// y2: 21*y2 ≡ 1 (mod 5) → y2 = 1
// y3: 15*y3 ≡ 1 (mod 7) → y3 = 1
// Step 4: Combine results
// x = a1*M1*y1 + a2*M2*y2 + a3*M3*y3
// x = 2*35*2 + 3*21*1 + 2*15*1
// x = 140 + 63 + 30 = 233
// Step 5: Final result
// x % M = 233 % 105 = 23
// So the solution is x = 23
// Note: For large k, consider using a more efficient algorithm or library for CRT to handle multiple equations efficiently.
//input format:
// Enter number of equations: 3
// Enter remainders and moduli:
// Equation 1: x % 3
// Remainder: 2
// Equation 2: x % 5
// Remainder: 3
// Equation 3: x % 7
// Remainder: 2






#include<bits/stdc++.h>
using namespace std;
long long CRT(vector<long long>& rem,vector<long long>& mod){
    long long product=1;
    for(auto m:mod) product*=m;
    long long result=0;
    for(int i=0;i<rem.size();i++){
        long long Mi=product/mod[i];
        long long yi=1;
        long long a=Mi,b=mod[i];
        long long m0=b,y=0,x=1;
        if(b==1) continue;
        while(a>1){
            long long q=a/b;
            long long t=b;
            b=a%b,a=t;
            t=y;
            y=x-q*y;
            x=t;
        }
        result+=(rem[i]*Mi*yi)%product;
    }
    return result;
}
int main(){
    int k;
    cout<<"Enter number of equations: ";
    cin>>k;
    vector<long long> rem(k),mod(k);
    cout<<"Enter remainders and moduli:\n";
    for(int i=0;i<k;i++){
        cout<<"Equation "<<i+1<<": x % ";
        cin>>mod[i];
        cout<<"Remainder: ";
        cin>>rem[i];
    }
    cout<<"Solution x = "<<CRT(rem,mod)<<endl;// Note: The solution is given modulo the product of the moduli.
    return 0;
}




//CRT 2nd method 
// ✅ 2) CORRECT CRT FORMULA

// For equations:

// x ≡ r1 (mod m1)
// x ≡ r2 (mod m2)
// ...

// Formula:
//x=summation of (ri * Mi * yi)mod M ,for i=1 to k, where Mi = M/mi and yi is the modular inverse of Mi mod mi, and M = m1*m2*...*mk
// where mi are the moduli and ri are the remainders
// where M = m1*m2*...*mk
// where mi are the moduli and ri are the remainders
//Mi=M/mi
//yi is the modular inverse of Mi mod mi
//yi=Mi^-1 mod mi
// Example: Solve x % 3 = 2, x % 5 = 3, x % 7 = 2
// Step 1: Calculate M = 3*5*7 = 105
// Step 2: Calculate Mi = M/mi
// M1 = 105/3 = 35
// M2 = 105/5 = 21
// M3 = 105/7 = 15
// Step 3: Calculate yi such that Mi*yi ≡ 1 (mod mi)
// y1: 35*y1 ≡ 1 (mod 3) → y1 = 2
// y2: 21*y2 ≡ 1 (mod 5) → y2 = 1
// y3: 15*y3 ≡ 1 (mod 7) → y3 = 1
// Step 4: Combine results
// x = a1*M1*y1 + a2*M2*y2 + a3*M3*y3
// x = 2*35*2 + 3*21*1 + 2*15*1
// x = 140 + 63 + 30 = 233
// Step 5: Final result
// x % M = 233 % 105 = 23
// So the solution is x = 23
// Note: The solution is given modulo the product of the moduli, so the final answer is x = 23 (mod 105).
// Note: For large k, consider using a more efficient algorithm or library for CRT to handle multiple equations efficiently.




#include<bits/stdc++.h>
using namespace std;

long long modInverse(long long a,long long mod){
    long long b=mod,u=1,v=0;
    while(b){
        long long t=a/b;
        a-=t*b; swap(a,b);
        u-=t*v; swap(u,v);
    }
    u%=mod;
    if(u<0) u+=mod;
    return u;
}

long long CRT(vector<long long>& rem, vector<long long>& mod){
    long long product=1;
    for(auto m:mod) product*=m;

    long long result=0;

    for(int i=0;i<rem.size();i++){
        long long Mi=product/mod[i];
        long long yi=modInverse(Mi,mod[i]);

        result=(result + rem[i]*Mi%product*yi)%product;
    }

    return (result+product)%product;
}

int main(){
    int k;
    cout<<"Enter number of equations: ";
    cin>>k;

    vector<long long> rem(k),mod(k);

    cout<<"Enter modulus and remainder:\n";
    for(int i=0;i<k;i++){
        cin>>mod[i]>>rem[i];
    }

    cout<<"Solution x = "<<CRT(rem,mod)<<endl;
}




// ⭐ 1.4 Wilson’s Theorem
// 💡 Formula

// For prime p:
// (p−1)!≡−1(modp)

// 🧠 Use
// primality proofs
// theoretical CP questions

// Rare but powerful.
// Example: Check if 7 is prime using Wilson's theorem
// Calculate (7-1)! = 6! = 720
// Since 720 % 7 = 6 and 6 ≡ -1 (mod 7), 7 is prime.
// Note: Wilson's theorem is not efficient for primality testing for large numbers, but it is a fundamental result in number theory and can be used in theoretical contexts or for small primes.
// Example: Check if 10 is prime using Wilson's theorem
// Calculate (10-1)! = 9! = 362880
// Since 362880 % 10 = 0 and 0 ≢ -1 (mod 10), 10 is not prime.
// Note: For large p, calculating (p-1)! can be computationally expensive, so Wilson's theorem is not practical for primality testing in competitive programming, but it serves as an important theoretical tool in number theory.
// Example: Check if 11 is prime using Wilson's theorem
// Calculate (11-1)! = 10! = 3628800
// Since 3628800 % 11 = 10 and 10 ≡ -1 (mod 11), 11 is prime.
// Note: Wilson's theorem is a fundamental result in number theory that provides a necessary and sufficient



#include<bits/stdc++.h>
using namespace std;
long long WilsonTheorem(int p){
    if(p<2) return 0; // Not prime
    long long fact=1;
    for(int i=2;i<p;i++){
        fact=(fact*i)%p;
    }
    return (fact==p-1) ? 1 : 0; // Returns 1 if prime, else 0
}
int main(){
    int n;
    cout<<"Enter a number: ";
    cin>>n;
    if(WilsonTheorem(n)){
        cout<<n<<" is a prime number."<<endl;
    } else {
        cout<<n<<" is not a prime number."<<endl;
    }
    return 0;
}





// ⭐ 2.1 Large Modular Exponentiation

// Used when exponent itself is huge.

// Use Euler theorem:
// a^b mod m = a^(b mod φ(m)) mod m,
// when coprime.
// Example: Compute 3^100 mod 10
// φ(10) = 4 (from previous example)
// Since gcd(3,10)=1, we can use Euler's theorem:
// 3^100 ≡ 3^(100 mod 4) (mod 10)
// 100 mod 4 = 0





#include<bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7; // Common modulus used in competitive programming
long long modExpEuler(long long a, long long b, int mod) {
    long long phi = mod - 1; // φ(mod) for prime mod is mod-1
    b = b % phi; // Reduce exponent using Euler's theorem
    long long res = 1;
    a = a % mod; // Handle cases where a >= mod
    while(b > 0) {
        if(b & 1) res = (res * a) % mod; // If b is odd, multiply a with result
        a = (a * a) % mod; // Square a
        b >>= 1; // Right shift b (divide by 2)
    }
    return res;
}
int main(){
    long long a, b;
    cout << "Enter base and exponent: ";
    cin >> a >> b;
    cout << a << " raised to the power " << b << " modulo " << MOD << " is: " << modExpEuler(a, b, MOD) << endl;
    return 0;
}





// ⭐ 2.2 Lucas Theorem ⭐⭐⭐
// 💡 Use

// For:
// nCr % p
// where n is huge (10^18).
// ⚙️ Formula
// Lucas Theorem states that for a prime p and non-negative integers n and r:
// nCr % p = Π (niCr_i) % p
// where ni and ri are the digits of n and r in base p representation.
//formula:C(n,r) mod p = Π C(ni,ri) mod p for all digits ni and ri of n and r in base p representation
// where ni and ri are the digits of n and r in base p representation.
// Base p decomposition.
//example: Compute C(10^18, 10^9) mod 7
// Step 1: Convert n and r to base 7
// n = 10^18 in base 7 = 2020202020202020202020
// r = 10^9 in base 7 = 2020202020
// Step 2: Apply Lucas Theorem
// C(10^18, 10^9) mod 7 = Π C(ni, ri) mod 7
// = C(2, 2) * C(0, 0) * C
//(2, 2) * C(0, 0) * C(2, 2) * C(0, 0) * C(2, 2) * C(0, 0) * C(2, 2) * C(0, 0) * C(2, 2) * C(0, 0) mod 7
// = 1 * 1 * 1 * 1 * 1 * 1 * 1 * 1 * 1 * 1 mod 7
// = 1
// So C(10^18, 10^9) mod 7 = 1
// Note: Lucas Theorem is particularly useful for computing binomial coefficients modulo a prime when n is very large, as it breaks down the problem into smaller subproblems based on the base p representation of n and r. This allows for efficient computation even when n is on the order of 10^18, which would be infeasible with direct factorial-based methods.
// Note: For large n and r, precompute factorials and inverse factorials modulo p for all digits up to p-1 to efficiently compute C(ni, ri) mod p for each digit pair in the base p representation of n and r.
// Example: Compute C(10^18, 10^9) mod 7 using precomputation
// Step 1: Precompute factorials and inverse factorials mod 7 for digits 0 to 6
// factorial[0] = 1
// factorial[1] = 1
// factorial[2] = 2
// factorial[3] = 6
// factorial[4] = 24
// factorial[5] = 120
// factorial[6] = 720
// inverse_factorial[0] = 1
// inverse_factorial[1] = 1
// inverse_factorial[2] = 4
// inverse_factorial[3] = 5
// inverse_factorial[4] = 3
// inverse_factorial[5] = 6
// inverse_factorial[6] = 2
// Step 2: Convert n and r to base 7
// n = 10^18 in base 7 = 2020202020202020202020
// r = 10^9 in base 7 = 2020202020





#include<bits/stdc++.h>
using namespace std;
long long modPow(long long a, long long b, int mod) {
    long long res = 1;
    a = a % mod; // Handle cases where a >= mod
    while(b > 0) {
        if(b & 1) res = (res * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}

long long smallNCR(int n,int r,int p){
    if(r>n) return 0;
    long long res=1;
    for(int i=0;i<r;i++){
        res=res*(n-i)%p;
        res=res*modPow(i+1,p-2,p)%p;
    }
    return res;
}

long long lucas(long long n,long long r,int p){
    if(r==0) return 1;
    return lucas(n/p,r/p,p)*smallNCR((int)(n%p),(int)(r%p),p)%p;
}
int main(){
    long long n,r;
    int p;
    cout<<"Enter n, r and prime modulus p: ";
    cin>>n>>r>>p;
    cout<<"C("<<n<<","<<r<<") mod "<<p<<" = "<<lucas(n,r,p)<<endl;
    return 0;
}




// ⭐ 3.1 Stars and Bars ⭐⭐⭐
// 💡 Problem

// Ways to distribute k identical items into n boxes.

// ⚙️ Formula

// Number of ways = C(n+k-1, k) = C(n+k-1, n-1)

// Where C is the binomial coefficient.

// 🧠 OA Usage
// distribute candies
// partition sums
// string construction
// Example: Distribute 5 identical candies into 3 boxes
// Here, n = 3 (boxes) and k = 5 (candies)
// Number of ways = C(3+5-1, 5) = C(7, 5) = 21
// So there are 21 ways to distribute 5 identical candies into 3 boxes.
// Note: The formula C(n+k-1, k) can be derived using the "stars and bars" combinatorial technique, where we represent the k identical items as stars and the n-1 dividers between boxes as bars. The total number of symbols (stars + bars) is n+k-1, and we need to choose k positions for the stars (or equivalently n-1 positions for the bars) to determine the distribution of items into boxes.
// Example: Distribute 4 identical balls into 2 boxes
// Here, n = 2 (boxes) and k = 4 (balls)
// Number of ways = C(2+4-1, 4) = C(5, 4) = 5
// So there are 5 ways to distribute 4 identical balls into 2 boxes.



#include<bits/stdc++.h>
using namespace std;

long long modPow(long long a, long long b, long long mod) {
    long long res = 1;
    a = a % mod;
    while(b > 0) {
        if(b & 1) res = (res * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}
long long smallNCR(long long n, long long r, long long p){
    if(r > n) return 0;
    long long res = 1;
    for(long long i = 0; i < r; i++){
        res = res * (n - i) % p;
        res = res * modPow(i + 1, p - 2, p) % p;
    }
    return res;
}
long long starsAndBars(int n, int k){
    if(n <= 0 || k < 0) return 0;
    return smallNCR(n + k - 1, k, 1e9 + 7);
}
int main(){
    int n, k;
    cout << "Enter number of boxes (n) and items (k): ";
    cin >> n >> k;
    cout << "Number of ways to distribute " << k << " identical items into " << n << " boxes is: " << starsAndBars(n, k) << endl;
    return 0;
}







// ⭐ 3.2 Catalan Numbers ⭐⭐⭐
// 💡 Use
// balanced parentheses
// BST count
// triangulation
// mountain arrays
// ⚙️ Formula

// C(n) = (2n)! / ((n+1)! * n!) = C(2n, n) - C(2n, n-1)
//for n>=0, C(n) = (2n)! / ((n+1)! * n!) = C(2n, n) - C(2n, n-1)
//formula other form: C(n) = C(2n, n) - C(2n, n-1)
//formula other form: C(n) = C(2n, n) / (n + 1)

// Where C is the binomial coefficient.
// Example: Count the number of valid parentheses combinations for n = 3
// Here, n = 3 (pairs of parentheses)
// C(3) = (2*3)! / ((3+1)! * 3!) = 6! / (4! * 3!) = 720 / (24 * 6) = 5
// So there are 5 valid combinations of parentheses for n = 3: "((()))", "(()())", "(())()", "()(())", "()()()"
// Note: Catalan numbers have a wide range of applications in combinatorial mathematics, including counting
// the number of ways to correctly match parentheses, the number of binary search trees with n nodes, the number of ways to triangulate a polygon with n+2 sides, and many other combinatorial structures. The nth Catalan number can be computed efficiently using dynamic programming or by using the formula involving binomial coefficients, as shown above.
// Example: Count the number of binary search trees with n = 4 nodes
// Here, n = 4 (nodes)
// C(4) = (2*4)! / ((4+1)! * 4!) = 8! / (5! * 4!) = 40320 / (120 * 24) = 14
// So there are 14 unique binary search trees that can be formed with 4 nodes.




#include<bits/stdc++.h>
using namespace std;

const long long MOD = 1e9 + 7;

long long modPow(long long a, long long b, long long mod) {
    long long res = 1;
    a = a % mod;
    while(b > 0) {
        if(b & 1) res = (res * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}
long long modInverseFermat(long long a, long long mod) {
    return modPow(a, mod - 2, mod);
}

long long nCr(int n, int r) {
    if(r > n) return 0;
    long long res = 1;
    for(int i = 0; i < r; i++) {
        res = res * (n - i) % MOD;
        res = res * modInverseFermat(i + 1, MOD) % MOD;
    }
    return res;
}

long long catalan(int n){
    return nCr(2*n,n)*modInverseFermat(n+1,MOD)%MOD;
}
int main(){
    int n;
    cout << "Enter n for Catalan number: ";
    cin >> n;
    cout << "The " << n << "th Catalan number is: " << catalan(n) << endl;
    return 0;
}




// ⭐ 3.3 Derangements
// 💡 Meaning

// Permutations where no element stays in original position.

// ⚙️ Formula
// D(n)=(n−1)(D(n−1)+D(n−2))
// D(0)=1,D(1)=0
// D(n) = (n-1) * (D(n-1) + D(n-2))
// with base cases D(0) = 1 and D(1) = 0
// Example: Count derangements of 4 items
// D(0) = 1
// D(1) = 0
// D(2) = (2-1) * (D(1) + D(0)) = 1 * (0 + 1) = 1
// D(3) = (3-1) * (D(2) + D(1)) = 2 * (1 + 0) = 2
// D(4) = (4-1) * (D(3) + D(2)) = 3 * (2 + 1) = 9
// So there are 9 derangements of 4 items.
// Note: Derangements are also known as "subfactorials" or "!" (exclamation mark) in combinatorics. The number of derangements of n items can also be computed using the formula D(n) = n! * (1 - 1/1! + 1/2! - 1/3! + ... + (-1)^n/n!), which is derived from the principle of inclusion-exclusion. This formula can be more efficient for large n when implemented with modular arithmetic to avoid overflow issues.
// Example: Count derangements of 5 items using the formula D(n) = n! * (1 - 1/1! + 1/2! - 1/3! + 1/4! - 1/5!)
// D(5) = 5! * (1 - 1/1! + 1/2! - 1/3! + 1/4! - 1/5!)
// D(5) = 120 * (1 - 1 + 0.5 - 0.1666667 + 0.0416667 - 0.0083333)
// D(5) = 120 * (0.375) = 45
// So there are 45 derangements of 5 items.



// 🚀 8) CP / OA USE CASES

// Derangements are common in:

// Secret Santa
// misplaced letters
// hat check problem
// seating arrangement
// permutations with restrictions
// probability problems


#include<bits/stdc++.h>
using namespace std;
long long derangement(int n){
    vector<long long> dp(n+1);
    dp[0]=1;
    dp[1]=0;
    for(int i=2;i<=n;i++)
        dp[i]=(i-1)*(dp[i-1]+dp[i-2]);
    return dp[n];
}
int main(){
    int n;
    cout<<"Enter number of items: ";
    cin>>n;
    cout<<"Number of derangements for "<<n<<" items is: "<<derangement(n)<<endl;
    return 0;
}





// 🔶 4) MATRIX EXPONENTIATION ⭐⭐⭐
// ⭐ 4.1 Fibonacci in log N
// 💡 Core Matrix


// | F(n)   | = | 1 1 |^(n-1) * | F(1) |
// | F(n-1) |   | 1 0 |           | F(0) |

// Where F(0)=0 and F(1)=1.
// ⚙️ Algorithm
// Define matrix multiplication and exponentiation.
// Use fast exponentiation to compute M^(n-1).
// Example: Compute F(10)
// Step 1: Define the transformation matrix M = | 1 1 |
//                                      | 1 0 |
// Step 2: Compute M^(10-1) = M^9 using fast exponentiation
// M^1 = | 1 1 |
//       | 1 0 |
// M^2 = M^1 * M^1 = | 2 1 |
//       | 1 0 |
// M^4 = M^2 * M^2 = | 5 3 |
//       | 3 2 |
// M^8 = M^4 * M^4 = | 34 21 |
//      | 21 13 |
// M^9 = M^8 * M^1 = | 55 34 |
//      | 34 21 |
// Step 3: F(10) = M^9[0][0] = 55
// So F(10) = 55
// Note: Matrix exponentiation can be applied to any linear recurrence relation, not just Fibonacci numbers. By defining the appropriate transformation matrix, you can compute the nth term of any linear recurrence in O(log n) time, which is much more efficient than the O(n) time required by naive recursive or iterative methods for large n.
// Example: Compute the nth term of the sequence defined by T(n) = 2*T(n-1) + 3*T(n-2) with T(0) = 1 and T(1) = 2
// Step 1: Define the transformation matrix M = | 2 3 |
//                                      | 1 0 |
// Step 2: Compute M^(n-1) using fast exponentiation
// Step 3: T(n) = M^(n-1)[0][0] * T(1) + M^(n-1)[0][1] * T(0)
// So T(n) can be computed efficiently for large n using matrix exponentiation.
// Note: When implementing matrix exponentiation, be mindful of the size of the numbers involved, as they can grow rapidly. Use modular arithmetic if the problem requires it to keep the numbers manageable and prevent overflow issues. Additionally, ensure that your matrix multiplication and exponentiation functions are optimized for performance, especially when dealing with large matrices or a large number of operations.
// Example: Compute T(10) for the sequence defined by T(n) = 2*T(n-1) + 3*T(n-2) with T(0) = 1 and T(1) = 2
// Step 1: Define the transformation matrix M = | 2 3 |
//                                      | 1 0 |
// Step 2: Compute M^(10-1) = M^9 using fast exponentiation
// M^1 = | 2 3 |
//       | 1 0 |
// M^2 = M^1 * M^1 = | 7 6 |
//       | 2 3 |
// M^4 = M^2 * M^2 = | 55 42 |
//       | 14 9 |
// M^8 = M^4 * M^4 = | 3025 2310 |
//      | 770  539 |
// M^9 = M^8 * M^1 = | 11015  6930 |
//      | 3025   2310 |
// Step 3: T(10) = M^9[0][0] * T(1) + M^9[0][1] * T(0) = 11015 * 2 + 6930 * 1 = 28960
// So T(10) = 28960



// 🧠 Use
// recurrence DP
// linear recurrence
// Fibonacci
// path counting



#include<bits/stdc++.h>
using namespace std;
struct Matrix{
    long long a[2][2];
};

Matrix mul(Matrix x,Matrix y){
    Matrix r={0};
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            for(int k=0;k<2;k++)
                r.a[i][j]+=x.a[i][k]*y.a[k][j];
    return r;
}

Matrix power(Matrix base,long long n){
    Matrix res={{{1,0},{0,1}}};
    while(n){
        if(n&1) res=mul(res,base);
        base=mul(base,base);
        n>>=1;
    }
    return res;
}
long long fibonacci(long long n){
    if(n==0) return 0;
    Matrix F={{{1,1},{1,0}}};
    Matrix Fn=power(F,n-1);
    return Fn.a[0][0];
}
int main(){
    long long n;
    cout<<"Enter n to compute F(n): ";
    cin>>n;
    cout<<"F("<<n<<") = "<<fibonacci(n)<<endl;
    return 0;
}



// 🔶 5) PROBABILITY & EXPECTED VALUE ⭐⭐⭐
// 💡 Expected Value Formula
// E[X] = Σ (x * P(X = x))
// Expected value (E[X]) is the sum of each possible outcome (x) multiplied by its probability (P(X = x)).
// Where E[X] is the expected value of the random variable X, x represents the possible outcomes, and P(X = x) is the probability of each outcome.

// 🧠 CP Usage
// random walks
// dice problems
// DP expectation
// game winning chance
// Example: Expected value of a dice roll
// A standard six-sided die has outcomes 1, 2, 3, 4, 5, and 6, each with a probability of 1/6.
// E[X] = (1 * 1/6) + (2 * 1/6) + (3 * 1/6) + (4 * 1/6) + (5 * 1/6) + (6 * 1/6)
// E[X] = (1 + 2 + 3 + 4 + 5 + 6) / 6
// E[X] = 21 / 6 = 3.5
// So the expected value of a dice roll is 3.5.
// Note: Expected value is a fundamental concept in probability theory and is widely used in competitive programming to solve problems involving randomness, such as calculating the average outcome of a random process, determining the expected number of steps to reach a certain state, or evaluating the expected winnings in a game. When solving such problems, it's important to carefully define the random variable and its possible outcomes, as well as to accurately calculate the probabilities associated with each outcome to ensure that the expected value is computed correctly.



#include<bits/stdc++.h>
using namespace std;
double expectedDice(){
    double ans=0;
    for(int i=1;i<=6;i++) ans+=i*(1.0/6);
    return ans;
}
int main(){
    cout<<"Expected value of a dice roll: "<<expectedDice()<<endl;
    return 0;
}




// 🔶 6) GAME THEORY ⭐⭐⭐



// ⭐ 6.1 Nim Game
// 💡 Rule
// XOR of piles.
// If XOR = 0 → losing state
// If XOR != 0 → winning state
// Example: 3 piles with 1, 4, and 5 stones
// XOR = 1 ^ 4 ^ 5 = 0 (losing state)
// So the player to move is in a losing position.
// Note: In the Nim game, players take turns removing any number of stones from a single pile. The player who takes the last stone wins. The key to determining the winning strategy is to calculate the XOR of the sizes of all piles. If the result is zero, it means that the current player is in a losing position, as any move they make will leave a non-zero XOR for the opponent. Conversely, if the XOR is non-zero, the current player has a winning strategy by making a move that results in a zero XOR for the opponent.
// Example: 3 piles with 2, 3, and 4 stones
// XOR = 2 ^ 3 ^ 4 = 5 (winning state)
// So the player to move is in a winning position and can make a move to create a losing state for the opponent.
// Note: The optimal strategy in Nim involves always trying to leave a position where the XOR of the piles is zero for the opponent. This can be achieved by calculating the XOR of the current piles and making a move that changes one of the piles to achieve a zero XOR. For example, if the current piles are 2, 3, and 4 (XOR = 5), the player can remove 1 stone from the pile of 4 to create piles of 2, 3, and 3 (XOR = 0), putting the opponent in a losing position.
// Example: 3 piles with 1, 2, and 3 stones
// XOR = 1 ^ 2 ^ 3 = 0 (losing state)
// So the player to move is in a losing position and any move they make will give a winning position to the opponent.
// Note: The Nim game is a classic example of a combinatorial game and serves as a fundamental building block for understanding more complex game theory problems. The concept of XOR and the winning strategy derived from it can be extended to other games with similar structures, making it an essential topic in competitive programming and algorithmic game theory.



#include<bits/stdc++.h>
using namespace std;
bool nimWin(vector<int>& piles){
    int xr=0;
    for(int x:piles) xr^=x;
    return xr!=0;
}

int main(){
    int n;
    cout<<"Enter number of piles: ";
    cin>>n;
    vector<int> piles(n);
    cout<<"Enter number of stones in each pile:\n";
    for(int i=0;i<n;i++) cin>>piles[i];
    if(nimWin(piles)){
        cout<<"First player has a winning strategy."<<endl;
    } else {
        cout<<"Second player has a winning strategy."<<endl;
    }
    return 0;
}




// ⭐ 6.2 Grundy Numbers
// 💡 Use
// Convert game to Nim.

// Very important for:

// graph games
// move games
// stone games
// Example: Consider a game where players take turns removing 1 or 2 stones from a pile. The player who takes the last stone wins. To determine the winning strategy, we can calculate the Grundy numbers for each possible pile size.
// Step 1: Define the Grundy number for a pile of size n as G(n).
// Step 2: Calculate G(n) for small values of n:
// G(0) = 0 (no moves possible)
// G(1) = 1 (remove 1 stone)
// G(2) = 1 (remove 2 stones)
// G(3) = 2 (remove 1 stone to leave G(2)
// G(4) = 2 (remove 2 stones to leave G(2))
// G(5) = 3 (remove 1 stone to leave G(4)
// G(6) = 3 (remove 2 stones to leave G(4))
// Step 3: The winning strategy is to always move to a position where the Grundy number is 0 for the opponent. For example, if the current pile size is 5 (G(5) = 3), the player can remove 1 stone to leave a pile of size 4 (G(4) = 2), which is a winning move since it leaves a non-zero Grundy number for the opponent.
// Note: Grundy numbers, also known as nimbers, are a powerful tool in combinatorial game theory for analyzing impartial games. By calculating the Grundy number for each position in the game, players can determine the optimal moves and strategies to win. The key idea is that a position with a Grundy number of 0 is a losing position, while any position with a non-zero Grundy number is a winning position. This allows players to make informed decisions based on the current state of the game and the possible moves available.
// Example: Consider a game where players take turns removing 1, 2, or 3 stones from a pile. The player who takes the last stone wins. To determine the winning strategy, we can calculate the Grundy numbers for each possible pile size.
// Step 1: Define the Grundy number for a pile of size n as G(n).
// Step 2: Calculate G(n) for small values of n:
// G(0) = 0 (no moves possible)
// G(1) = 1 (remove 1 stone)
// G(2) = 1 (remove 2 stones)
// G(3) = 1 (remove 3 stones)
// G(4) = 2 (remove 1 stone to leave G(3)
// G(5) = 2 (remove 2 stones to leave G(3)
// G(6) = 2 (remove 3 stones to leave G(3)
// G(7) = 3 (remove 1 stone to leave G(6)
// G(8) = 3 (remove 2 stones to leave G(6)
// G(9) = 3 (remove 3 stones to leave G(6)
// Step 3: The winning strategy is to always move to a position where the Grundy number is 0 for the opponent. For example, if the current pile size is 7 (G(7) = 3), the player can remove 1 stone to leave a pile of size 6 (G(6) = 2), which is a winning move since it leaves a non-zero Grundy number for the opponent.
// Note: In more complex games, such as those involving multiple piles or more intricate move rules, the calculation of Grundy numbers can become more involved. However, the underlying principle remains the same: by determining the Grundy number for each position, players can identify winning and losing positions and develop optimal strategies accordingly. This makes Grundy numbers an essential concept in the analysis of combinatorial games and a valuable tool for competitive programmers tackling game theory problems.

#include<bits/stdc++.h>
using namespace std;
int grundy(int n){
    if(n==0) return 0;
    vector<int> moves={1,2,3}; // Example moves: remove 1, 2, or 3 stones
    set<int> nextStates;
    for(int move:moves){
        if(n-move>=0) nextStates.insert(grundy(n-move));
    }
    int g=0;
    while(nextStates.count(g)) g++;
    return g;
}
int main(){
    int n;
    cout<<"Enter number of stones: ";
    cin>>n;
    if(grundy(n)!=0){
        cout<<"First player has a winning strategy."<<endl;
    } else {
        cout<<"Second player has a winning strategy."<<endl;
    }
    return 0;
}



// ⭐ 6.3 Sprague-Grundy Theorem
// 💡 Use
// Combine multiple games into one Nim game.
// Example: Consider two independent games, Game A and Game B. In Game A, players take turns removing 1 or 2 stones from a pile of 5 stones. In Game B, players take turns removing 1 or 3 stones from a pile of 7 stones. To determine the winning strategy for the combined game, we can calculate the Grundy numbers for each game and then combine them using the Sprague-Grundy theorem.
// Step 1: Calculate the Grundy numbers for Game A (pile of 5 stones):
// G_A(0) = 0 (no moves possible)
// G_A(1) = 1 (remove 1 stone)
// G_A(2) = 1 (remove 2 stones)
// G_A(3) = 2 (remove 1 stone to leave G_A(2))
// G_A(4) = 2 (remove 2 stones to leave G_A(2))
// G_A(5) = 3 (remove 1 stone to leave G_A(4))
// Step 2: Calculate the Grundy numbers for Game B (pile of 7 stones):
// G_B(0) = 0 (no moves possible)
// G_B(1) = 1 (remove 1 stone)
// G_B(2) = 1 (remove 3 stones, not possible)
// G_B(3) = 2 (remove 1 stone to leave G_B(2))
// G_B(4) = 2 (remove 3 stones to leave G_B(1))
// G_B(5) = 3 (remove 1 stone to leave G_B(4))
// G_B(6) = 3 (remove 3 stones to leave G_B(3))
// G_B(7) = 4 (remove 1 stone to leave G_B(6))
// Step 3: Combine the Grundy numbers using XOR to determine the winning strategy for the combined game:
// G_combined = G_A(5) XOR G_B(7) = 3 XOR 4 = 7 (non-zero)
// So the first player has a winning strategy in the combined game.
// Note: The Sprague-Grundy theorem states that any impartial game can be reduced to a Nim game by calculating the Grundy numbers for each position in the game. By combining the Grundy numbers of multiple independent games using the XOR operation, we can determine the overall winning strategy for the combined game. This is a powerful tool in combinatorial game theory, allowing us to analyze complex games by breaking them down into simpler components and applying the principles of Nim to find optimal strategies for players.
// Example: Consider three independent games, Game A, Game B, and Game C. In Game A, players take turns removing 1 or 2 stones from a pile of 4 stones. In Game B, players take turns removing 1 or 3 stones from a pile of 6 stones. In Game C, players take turns removing 2 or 4 stones from a pile of 8 stones. To determine the winning strategy for the combined game, we can calculate the Grundy numbers for each game and then combine them using the Sprague-Grundy theorem.
// Step 1: Calculate the Grundy numbers for Game A (pile of 4 stones):
// G_A(0) = 0 (no moves possible)
// G_A(1) = 1 (remove 1 stone)
// G_A(2) = 1 (remove 2 stones)
// G_A(3) = 2 (remove 1 stone to leave G_A(2))
// G_A(4) = 2 (remove 2 stones to leave G_A(2))
// Step 2: Calculate the Grundy numbers for Game B (pile of 6 stones):
// G_B(0) = 0 (no moves possible)
// G_B(1) = 1 (remove 1 stone)




#include<bits/stdc++.h>
using namespace std;
int grundyA(int n){
    if(n==0) return 0;
    vector<int> moves={1,2}; // Example moves for Game A: remove 1 or 2 stones
    set<int> nextStates;
    for(int move:moves){
        if(n-move>=0) nextStates.insert(grundyA(n-move));
    }
    int g=0;
    while(nextStates.count(g)) g++;
    return g;
}
int grundyB(int n){
    if(n==0) return 0;
    vector<int> moves={1,3}; // Example moves for Game B: remove 1 or 3 stones
    set<int> nextStates;
    for(int move:moves){
        if(n-move>=0) nextStates.insert(grundyB(n-move));
    }
    int g=0;
    while(nextStates.count(g)) g++;
    return g;
}
int main(){
    int pileA, pileB;
    cout<<"Enter number of stones in Game A: ";
    cin>>pileA;
    cout<<"Enter number of stones in Game B: ";
    cin>>pileB;
    
    int gA = grundyA(pileA);
    int gB = grundyB(pileB);
    
    if((gA ^ gB) != 0){
        cout<<"First player has a winning strategy."<<endl;
    } else {
        cout<<"Second player has a winning strategy."<<endl;
    }
    return 0;
}





// ⭐ 7.1 FFT ⭐⭐⭐
// 💡 Use

// Fast polynomial multiplication.

// Complexity:

// O(N log N)

// instead of O(N²).

// 🧠 Usage
// convolution
// string matching
// big integer multiplication
// Example: Multiply two polynomials A(x) = 1 + 2x + 3x² and B(x) = 4 + 5x
// Step 1: Represent the polynomials as coefficient arrays:
// A = [1, 2, 3] (represents 1 + 2x + 3x²)
// B = [4, 5] (represents 4 + 5x)
// Step 2: Use FFT to compute the convolution of A and B, which gives the coefficients of the resulting polynomial C(x) = A(x) * B(x).
// C = [4, 13, 22, 15] (represents 4 + 13x + 22x² + 15x³)
// So the resulting polynomial is C(x) = 4 + 13x + 22x² + 15x³.
// Note: The Fast Fourier Transform (FFT) is an efficient algorithm for computing the discrete Fourier transform (DFT) and its inverse. In the context of polynomial multiplication, FFT allows us to compute the convolution of two polynomials in O(N log N) time, which is significantly faster than the naive O(N²) approach. This is particularly useful when dealing with large polynomials, as it enables us to perform multiplications that would otherwise be computationally infeasible. The key idea behind FFT is to evaluate the polynomials at specific points (roots of unity) and then use these evaluations to reconstruct the coefficients of the resulting polynomial after multiplication. This technique is widely used in competitive programming for problems involving polynomial operations, string matching, and big integer arithmetic.
// Example: Perform string matching using FFT
// Given a text T = "ababc" and a pattern P = "abc", we want to find all occurrences of P in T using FFT.
// Step 1: Represent the text and pattern as binary arrays based on character presence:
// T = [1, 1, 0, 1, 0] (represents 'a', 'b', 'a', 'b', 'c')
// P = [1, 0, 1] (represents 'a', 'b', 'c')
// Step 2: Reverse the pattern array and perform convolution with the text array using FFT:
// Reversed P = [1, 0, 1]
// Convolution result = [1, 0, 2, 0, 1] (represents the number of matches at each position)
// Step 3: Analyze the convolution result to find matches:
// The convolution result indicates that there is a match of the pattern P in the text T at positions where the value is equal to the length of the pattern (in this case, 3). In this example, we find a match at position 2 (0-based index), which corresponds to the substring "abc" in T.
// So the pattern P occurs in the text T at position 2.






#include<bits/stdc++.h>
using namespace std;
const double PI = acos(-1);
void fft(vector<complex<double>>& a, bool invert) {
    int n = a.size();
    if (n == 1) return;

    vector<complex<double>> a0(n / 2), a1(n / 2);
    for (int i = 0; i < n / 2; i++) {
        a0[i] = a[2*i];
        a1[i] = a[2*i + 1];
    }
    fft(a0, invert);
    fft(a1, invert);

    double ang = 2 * PI / n * (invert ? -1 : 1);
    complex<double> w(1), wn(cos(ang), sin(ang));
    for (int i = 0; i < n / 2; i++) {
        a[i] = a0[i] + w * a1[i];
        a[i + n/2] = a0[i] - w * a1[i];
        if (invert) {
            a[i] /= 2;
            a[i + n/2] /= 2;
        }
        w *= wn;
    }
}
vector<int> multiply(const vector<int>& a, const vector<int>& b) {
    vector<complex<double>> fa(a.begin(), a.end()), fb(b.begin(), b.end());
    int n = 1;
    while (n < a.size() + b.size()) n <<= 1;
    fa.resize(n);
    fb.resize(n);

    fft(fa, false);
    fft(fb, false);
    for (int i = 0; i < n; i++) fa[i] *= fb[i];
    fft(fa, true);

    vector<int> result(n);
    for (int i = 0; i < n; i++) result[i] = round(fa[i].real());
    return result;
}
int main() {
    vector<int> A = {1, 2, 3}; // Represents 1 + 2x + 3x²
    vector<int> B = {4, 5};    // Represents 4 + 5x

    vector<int> C = multiply(A, B); // C will represent the coefficients of the resulting polynomial

    cout << "Resulting polynomial coefficients: ";
    for (int coeff : C) {
        cout << coeff << " ";
    }
    cout << endl;
    return 0;
}





// 🚀 INTERVIEW THINKING

// Whenever brute force seems impossible, think:

// Can math reduce complexity?
// Can recurrence become matrix?
// Can counting become combinatorics?
// Can game become XOR?

// That is elite CP thinking.