src/math/twelvefoldway.hpp

• View this file on GitHub
• Last update: 2026-01-30 22:16:29+09:00
• Include: #include "src/math/twelvefoldway.hpp"

Depends on

• src/math/combination.hpp
• src/template.hpp

Code

#pragma once
#include "combination.hpp"

template<typename T>
struct Twelvefoldway:Combination<T> {
    using Combination<T>::Combination;

    // (玉を区別しない, 玉を区別する) x (箱を区別しない, 箱を区別する) x (1個以内, 制限無し, 1個以上)
    T f000(int n,int k){
        return (n<=k);
    }
    T f001(int n,int k){
        //分割数
        vector<vector<T>> dp(k+1,vector<T>(n+1,0));
        dp[0][0]=1;
        rep(i,k){
            rep(j,n+1){
                if(j-i-1>=0){
                    dp[i+1][j]=dp[i][j]+dp[i][j-i-1];
                }
                else{
                    dp[i+1][j]=dp[i][j];
                }
            }
        }
        return dp[k][n];

    }
    T f002(int n,int k){
        if(n<k) return 0;
        return f001(n-k,k);
    }
    T f010(int n,int k){
        return this->C(k,n);
    }
    T f011(int n,int k){
        return this->H(k,n);
    }

    T f012(int n,int k){
        return this->C(n-1,k-1);
    }

    T f100(int n,int k){
        return (n<=k);
    }
    T f101(int n,int k){
        //ベル数
        vector<T> b(k+2,0);
        rep(i,k+1) b[i+1]=b[i]+this->ifact(k)*(i%2*2-1);
        T ret=0;
        rep(i,k+1) ret+=T(i).pow(n)*this->ifact(i)*b[k+1-i];
        return ret;
    }
    T f102(int n,int k){
        //第二種スターリング数
        return f112(n,k)*this->ifact(k);
    }

    T f110(int n,int k){
        return this->P(k,n);
    }
    T f111(int n,int k){
        return T(k).pow(n);
    }
    T f112(int n,int k){
        if(n<k) return 0;
        T ret=0;
        rep(i,k+1) ret+=((k-i)%2*2-1)*this->C(k,i)*T(i).pow(n);
        return ret;
    }
};

#line 2 "src/template.hpp"
#include <bits/stdc++.h>
using namespace std;
#define si(a) (long)a.size()
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<(int)(n);++i)
template<typename S,typename F> bool chmin(S&a,F b){return b<a?(a=b,1):0;}
template<typename S,typename F> bool chmax(S&a,F b){return b>a?(a=b,1):0;}
bool _=(ios::sync_with_stdio(0),cin.tie(0),cout<<fixed<<setprecision(16),0);
#line 3 "src/math/combination.hpp"

template<typename T>
struct Combination {
    vector<T> fa{},ifa{};
    Combination(int n){
        fa.resize(n+1);
        ifa.resize(n+1);
        fa[0]=1;
        for(int i=1;i<=n;i++) fa[i]=fa[i-1]*i;
        ifa[n]=fa[n].inv();
        for(int i=n;i>=1;i--) ifa[i-1]=ifa[i]*i;
    }

    T fact(int n){
        if(n<0) return T(0);
        return fa[n];
    }

    T ifact(int n){
        if(n<0) return T(0);
        return ifa[n];
    }

    T C(int n,int k){
        if(k<0||k>n) return 0;
        return fact(n)*ifact(k)*ifact(n-k);
    }
    T H(int n,int k){
        if(n==0&&k==0) return 1;
        if(n<=0||k<0) return 0;
        return C(n+k-1,k);
    }
    T P(int n,int k){
        if(k<0||k>n) return 0;
        return fact(n)*ifact(n-k);
    }
    // n<=m+K
    T Kata(int n,int m,int k){
        if(n>m+k) return 0;
        return C(n+m,n)-C(n+m,n-k-1);
    };
    // n個の箱にk個の玉を入れる。各箱は最大でr個しか入れれない
    T limC(int n,int k,int r){
        T ret=0;
        rep(i,k/(r+1)+1){
            ret+=((i%2==0)*2-1)*C(n,i)
                  *C(n+k-1-i*(r+1),n-1);
        }
        return ret;
    }
};
#line 3 "src/math/twelvefoldway.hpp"

template<typename T>
struct Twelvefoldway:Combination<T> {
    using Combination<T>::Combination;

    // (玉を区別しない, 玉を区別する) x (箱を区別しない, 箱を区別する) x (1個以内, 制限無し, 1個以上)
    T f000(int n,int k){
        return (n<=k);
    }
    T f001(int n,int k){
        //分割数
        vector<vector<T>> dp(k+1,vector<T>(n+1,0));
        dp[0][0]=1;
        rep(i,k){
            rep(j,n+1){
                if(j-i-1>=0){
                    dp[i+1][j]=dp[i][j]+dp[i][j-i-1];
                }
                else{
                    dp[i+1][j]=dp[i][j];
                }
            }
        }
        return dp[k][n];

    }
    T f002(int n,int k){
        if(n<k) return 0;
        return f001(n-k,k);
    }
    T f010(int n,int k){
        return this->C(k,n);
    }
    T f011(int n,int k){
        return this->H(k,n);
    }

    T f012(int n,int k){
        return this->C(n-1,k-1);
    }

    T f100(int n,int k){
        return (n<=k);
    }
    T f101(int n,int k){
        //ベル数
        vector<T> b(k+2,0);
        rep(i,k+1) b[i+1]=b[i]+this->ifact(k)*(i%2*2-1);
        T ret=0;
        rep(i,k+1) ret+=T(i).pow(n)*this->ifact(i)*b[k+1-i];
        return ret;
    }
    T f102(int n,int k){
        //第二種スターリング数
        return f112(n,k)*this->ifact(k);
    }

    T f110(int n,int k){
        return this->P(k,n);
    }
    T f111(int n,int k){
        return T(k).pow(n);
    }
    T f112(int n,int k){
        if(n<k) return 0;
        T ret=0;
        rep(i,k+1) ret+=((k-i)%2*2-1)*this->C(k,i)*T(i).pow(n);
        return ret;
    }
};

Back to top page