I want to let you know that this is not a tutorial blog. There are already plenty of well-written tutorials (including video tutorials) available out there. This blog is focused exclusively on the implementation, assuming that you are already well-versed in Tries and Bit Tries.

This blog is intended for those seeking the template, and it also includes additional valuable content. Please ensure to read the entire blog.

Recently, I encountered a problem that could be solved using a Trie. This sparked my interest in learning the data structure to tackle that specific problem.

However, I soon realized that nearly every tutorial out there implements a Trie using pointers. Out of curiosity, I wanted to explore how to implement it without using pointers. I searched extensively online but, surprisingly, found no clear guidance.

Eventually, I decided to implement it on my own — and that’s exactly what led to the creation of this blog.

#ifdef INSANE
#define dbg(x...) cerr << #x << " : ["; _print(x)
#else
#define dbg(x...)
#endif

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "T" : "F");}

template <typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template <typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
void __print(vector<bool> &v) {int f = 0; cerr << '{'; for (auto &&i : v) cerr << (f++ ? "," : "") << (i ? "T" : "F"); cerr << "}";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
template <size_t N> void __print(bitset<N> x) {cerr << x;}

vector<int> primes, lp, pf;

void Sieve(int n){
    lp.assign(n+1, 0);
    pf.assign(n+1, 0);
    primes.clear();

    for(int i=2; i<=n; i++){
        if(!lp[i]){
            primes.pb(i);
            lp[i] = i;
            pf[i] = 1;
        }
        for(auto &p : primes){
            if(i*p > n) break;
            lp[i*p] = p;
            if(p == lp[i]){
                pf[i*p] = pf[i];
                break;
            }
            pf[i*p] = pf[i] + 1;
        }
        // pf[i] += pf[i-1];
    }
}

template <typename T>
constexpr T power(ll a, T b, ull res = 1){
    a %= M;
    while(b){
        if(b&1) (res *= a) %= M;
        (a *= a) %= M;
        b >>= 1;
    }
    return res;
}

template <typename T>
constexpr T power(ll a, T b, ull res = 1){
    a %= M;
    while(b){
        if(b&1) (res *= a) %= M;
        (a *= a) %= M;
        b >>= 1;
    }
    return res;
}

template <typename T>
constexpr T inverse(T x) {return power(x, M-2);}

struct Comb {
    int n;
    vector<int> _fact, _invfact, _inv;

    Comb() : n{0}, _fact{1}, _invfact{1}, _inv{0} {}
    Comb(int _n) : Comb() {init(_n);}

    void init(int m){
        _fact.resize(m+1);
        _invfact.resize(m+1);
        _inv.resize(m+1);

        for(int i=n+1; i<=m; i++){
            _fact[i] = 1LL*_fact[i-1]*i%M;
        }
        _invfact[m] = inverse(_fact[m]);
        for(int i=m; i>n; i--){
            _invfact[i-1] = 1LL*_invfact[i]*i%M;
            _inv[i] = 1LL*_invfact[i]*_fact[i-1]%M;
        }
        n = m;
    }

    int fact(int m){
        if(m > n) init(2*m);
        return _fact[m];
    }

    int invfact(int m){
        if(m > n) init(2*m);
        return _invfact[m];
    }

    int inv(int m){
        if(m > n) init(2*m);
        return _inv[m];
    }

    int binom(int n, int r){
        if(n < r || r < 0) return 0;
        return 1LL*fact(n)*invfact(r)%M*1LL*invfact(n-r)%M;
    }
} comb;