library

This documentation is automatically generated by online-judge-tools/verification-helper

---

Project maintained by tko919 Hosted on GitHub Pages — Theme by mattgraham

$q$-binomial
(Math/qbinom.hpp)

• View this file on GitHub
• Last update: 2024-06-22 00:56:30+09:00
• Include: #include "Math/qbinom.hpp"

Code

#pragma once

template<typename T>struct QBinom{
    int ord;
    vector<T> fact,ifact;
    QBinom(T q,int sz){
        vector<T> base;
        T x=1;
        rep(i,0,sz){
            base.push_back(x);
            x=x*q+1;
            if(x==0)break;
        }
        ord=SZ(base);
        fact.push_back(1);
        rep(i,0,ord){
            fact.push_back(fact.back()*base[i]);
        }
        ifact.push_back(T(1)/fact.back());
        rrep(i,0,ord){
            ifact.push_back(ifact.back()*base[i]);
        }
        reverse(ALL(ifact));
        ord++;
        show(fact,ifact,ord);
    }  
    T binom(int n,int r){
        if(r<0 or n<r)return 0;
        if(n<ord)return fact[n]*ifact[r]*ifact[n-r];
        
        int n1=n/ord,n2=n%ord;
        int r1=r/ord,r2=r%ord;
        return nCr<T>(n1, r1) * binom(n2, r2);
    }
};

/**
 * @brief $q$-binomial
 */

#line 2 "Math/qbinom.hpp"

template<typename T>struct QBinom{
    int ord;
    vector<T> fact,ifact;
    QBinom(T q,int sz){
        vector<T> base;
        T x=1;
        rep(i,0,sz){
            base.push_back(x);
            x=x*q+1;
            if(x==0)break;
        }
        ord=SZ(base);
        fact.push_back(1);
        rep(i,0,ord){
            fact.push_back(fact.back()*base[i]);
        }
        ifact.push_back(T(1)/fact.back());
        rrep(i,0,ord){
            ifact.push_back(ifact.back()*base[i]);
        }
        reverse(ALL(ifact));
        ord++;
        show(fact,ifact,ord);
    }  
    T binom(int n,int r){
        if(r<0 or n<r)return 0;
        if(n<ord)return fact[n]*ifact[r]*ifact[n-r];
        
        int n1=n/ord,n2=n%ord;
        int r1=r/ord,r2=r%ord;
        return nCr<T>(n1, r1) * binom(n2, r2);
    }
};

/**
 * @brief $q$-binomial
 */

Back to top page