登录
← 返回首页 | 代码片段 › 7 数论与数学 › 7.2 组合数学与计数 › 组合数学与计数 / 搜索
JSON MD

7.2 组合数学与计数

组合数学 Comb
167 行
CPP JSON
【组合数学工具类 Combinatorics】 ▪ Combinatorics(n) — 构造函数,预处理 [0,n] 的阶乘 fact[] 和逆阶乘 inv_fact[],O(N) ▪ qpow(a, b) — 快速幂(内部使用),用于求逆元,O(log MOD) ▪ inv(x) — 求 x 的模逆元:qpow(x, MOD-2)(费马小定理,需 MOD 为质数) ▪ C(n, k) — 组合数 C(n,k) = fact[n] * inv_fact[k] * inv_fact[n-k] % MOD,O(1) ▪ A(n, k) — 排列数 A(n,k) = fact[n] * inv_fact[n-k] % MOD,O(1) ▪ Lucas(n, k) — 卢卡斯定理求 C(n,k)%MOD,适用于 n,k 很大但 MOD 较小(质数),O(log_MOD n) ▪ Stirling2(n, k) — 第二类斯特林数 S(n,k),n 个元素划分为 k 个非空子集的方案数,O(nk)
C++ 167 行 CPP
class Combinatorics {
private:
    vector<ll> fact, inv_fact;
    int max_n;
    
public:
    // 预处理阶乘和逆阶乘,O(n)
    Combinatorics(int n) : max_n(n) {
        fact.resize(n + 1);
        inv_fact.resize(n + 1);
        
        fact[0] = 1;
        for (int i = 1; i <= n; i++) {
            fact[i] = fact[i - 1] * i % MOD;
        }
        
        inv_fact[n] = inv(fact[n]);
        for (int i = n - 1; i >= 0; i--) {
            inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD;
        }
    }
    
    // 快速幂计算逆元,O(log MOD)
    ll inv(ll x) {
        return qpow(x, MOD - 2);
    }
    
    // 快速幂,O(log exponent)
    ll qpow(ll a, ll b) {
        ll res = 1;
        while (b) {
            if (b & 1) res = res * a % MOD;
            a = a * a % MOD;
            b >>= 1;
        }
        return res;
    }
    
    // 组合数C(n,k),O(1)
    ll C(int n, int k) {
        if (k < 0 || k > n) return 0;
        return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD;
    }
    
    // 排列数A(n,k),O(1)
    ll A(int n, int k) {
        if (k < 0 || k > n) return 0;
        return fact[n] * inv_fact[n - k] % MOD;
    }
    
    // 卢卡斯定理计算组合数,适用于n,k很大但MOD较小的情况
    ll Lucas(ll n, ll k) {
        if (k == 0) return 1;
        return C(n % MOD, k % MOD) * Lucas(n / MOD, k / MOD) % MOD;
    }
    
    // 第二类斯特林数S(n,k),将n个元素划分为k个非空子集,O(nk)
    ll Stirling2(int n, int k) {
        ll res = 0;
        for (int i = 0; i <= k; i++) {
            ll term = C(k, i) * qpow(i, n) % MOD;
            if ((k - i) % 2) {
                res = (res - term + MOD) % MOD;
            } else {
                res = (res + term) % MOD;
            }
        }
        return res * inv_fact[k] % MOD;
    }
    
    // 贝尔数B(n),基于第二类斯特林数的实现,O(n^2)
    // B(n) = Σ S(n,k) for k=0 to n
    ll Bell_Stirling(int n) {
        ll res = 0;
        for (int k = 0; k <= n; k++) {
            res = (res + Stirling2(n, k)) % MOD;
        }
        return res;
    }
    
    // 贝尔数B(n),基于动态规划的实现,O(n^2)
    // 使用递推关系:B(n+1) = Σ C(n,k)*B(k) for k=0 to n
    ll Bell_DP(int n) {
        if (n == 0) return 1;
        vector<ll> bell(n + 1);
        bell[0] = 1;
        
        for (int i = 1; i <= n; i++) {
            bell[i] = 0;
            for (int k = 0; k < i; k++) {
                bell[i] = (bell[i] + C(i - 1, k) * bell[k]) % MOD;
            }
        }
        return bell[n];
    }
    
    // 卡特兰数,O(1)
    ll Catalan(int n) {
        return C(2 * n, n) * inv(n + 1) % MOD;
    }
    
    // 错位排列数,O(n)预处理后O(1)查询
    ll Derangement(int n) {
        if (n == 0) return 1;
        if (n == 1) return 0;
        // D(n) = (n-1)*(D(n-1)+D(n-2))
        vector<ll> d(n + 1);
        d[0] = 1;
        d[1] = 0;
        for (int i = 2; i <= n; i++) {
            d[i] = (i - 1) * (d[i - 1] + d[i - 2]) % MOD;
        }
        return d[n];
    }
    
    // 计算gcd,O(log min(a,b))
    ll gcd(ll a, ll b) {
        return b == 0 ? a : gcd(b, a % b);
    }
    
    // 计算lcm,O(log min(a,b))
    ll lcm(ll a, ll b) {
        return a / gcd(a, b) * b;
    }
    
    // 扩展欧几里得算法,求解ax + by = gcd(a,b)
    ll ext_gcd(ll a, ll b, ll &x, ll &y) {
        if (b == 0) {
            x = 1;
            y = 0;
            return a;
        }
        ll d = ext_gcd(b, a % b, y, x);
        y -= a / b * x;
        return d;
    }
    
    // 中国剩余定理,求解x ≡ a_i (mod m_i)
    ll CRT(const vector<ll> &a, const vector<ll> &m) {
        ll M = 1, x = 0;
        int n = a.size();
        for (int i = 0; i < n; i++) M *= m[i];
        
        for (int i = 0; i < n; i++) {
            ll Mi = M / m[i];
            ll y, z;
            ext_gcd(Mi, m[i], y, z);
            x = (x + a[i] * Mi % M * y % M) % M;
        }
        return (x + M) % M;
    }
    
    // 欧拉函数,计算小于n且与n互质的数的个数,O(sqrt(n))
    ll EulerPhi(ll n) {
        ll res = n;
        for (ll i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                res = res / i * (i - 1);
                while (n % i == 0) n /= i;
            }
        }
        if (n > 1) res = res / n * (n - 1);
        return res;
    }
};

Combinatorics comb(1000000); // 预处理1e6以内的阶乘
Polya定理 mi
47 行
CPP JSON
【Polya定理】 组合数学与计数模板。 核心函数: void in(Re &x) — 核心算法函数 int mi(Re x,Re k) — 核心算法函数 int inv(Re x) — 求模逆元 int phi(Re x) — 核心算法函数 关键配置: N=1e6+3,P=1e9+7 说明:freopen("123.txt","r",stdin); 适用场景:计数问题、排列组合求值(含模运算)
C++ 46 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1e6+3,P=1e9+7;
int n,T,pri[N/3];bool pan[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int mi(Re x,Re k){
	Re s=1;
	while(k){
		if(k&1)s=(LL)s*x%P;
		x=(LL)x*x%P,k>>=1;
	}
	return s;
}
inline int inv(Re x){return mi(x,P-2);}
inline int phi(Re x){
	Re ans=x;
	for(Re i=2;i*i<=x;i++)
		if(x%i==0){
			ans/=i,ans*=i-1;
			while(x%i==0)x/=i;
		}
	if(x>1)ans/=x,ans*=x-1;
	return ans;
}
int main(){
//	freopen("123.txt","r",stdin);
	in(T);
	while(T--){
		in(n);Re ans=0;
		for(Re i=1;i*i<=n;++i)
			if(n%i==0){
				(ans+=(LL)mi(n,i-1)*phi(n/i)%P)%=P;
				if(i!=n/i)(ans+=(LL)mi(n,n/i-1)*phi(i)%P)%=P;
			}
		printf("%d\n",ans);
	}
}
卡特兰数Catalan 质因数分解 取模
25 行
CPP JSON
【卡特兰数Catalan(质因数分解 取模)】 卡特兰数(Catalan Number)模板,常见于括号序列、出栈序列等计数。 核心函数: void get_pri(Re N) — 获取值 LL Catalan(Re n) — 核心算法函数 关键配置: N=1e6+3 适用场景:计数问题、排列组合求值(含模运算)
C++ 24 行 CPP
#include<cstdio>
#define LL long long
#define Re register LL
const int N=1e6+3;
LL n,P,cnt,pri[N],pan[N<<1];
inline void get_pri(Re N){
    for(Re i=2;i<=N;++i){
        if(!pan[i])pri[++cnt]=i;
        for(Re j=1;j<=cnt&&i*pri[j]<=N;++j)pan[i*pri[j]]=1;
    }
}
inline LL Catalan(Re n){
    Re ans=1;cnt=0;get_pri(n<<1);
    for(Re i=1;i<=cnt;i++){
        Re x=pri[i],t=0;
        while(x<=2*n){t+=2*n/x-n/x-(n+1)/x;x*=pri[i];}
        while(t--)(ans*=pri[i])%=P;
    }
    return ans%P;
}
int main(){
    scanf("%lld%lld",&n,&P);
	printf("%lld",Catalan(n));
}
卡特兰数Catalan 质因数分解 高精度
22 行
CPP JSON
【卡特兰数Catalan(质因数分解 高精度)】 卡特兰数(Catalan Number)模板,常见于括号序列、出栈序列等计数。 核心函数: void cf(int x) — 核心算法函数 适用场景:计数问题、排列组合求值(含模运算)
C++ 21 行 CPP
#include<cstdio>
#define R register int
int n,t,x,len,ans[100000],pan[120005];
void cf(int x){
    R i,j;
    for(i=1;i<=len;i++)ans[i]*=x;
    len+=6;
    for(i=1;i<=len;i++)ans[i+1]+=ans[i]/10,ans[i]%=10;
    while(!ans[len])len--;
}
int main(){
    scanf("%d",&n);R i,j;len=ans[1]=1;
    for(i=2;i<=2*n;i++)
        if(pan[i]==0){
            x=i;t=0;
            while(x<=2*n){t+=2*n/x-n/x-(n+1)/x;x*=i;}
            while(t--)cf(i);
            for(j=i;j<=2*n/i;j++)pan[i*j]=1;
        }
    for(i=len;i>=1;i--)printf("%d",ans[i]);
}
卢卡斯定理 mi
37 行
CPP JSON
【卢卡斯定理】 Lucas 定理模板,用于大组合数对质数取模。 核心函数: void in(Re &x) — 核心算法函数 int mi(Re x,Re k) — 核心算法函数 int inv(Re x) — 求模逆元 int C(Re m,Re n) — 核心算法函数 int Lucas(Re m,Re n) — 卢卡斯定理 关键配置: N=1e5+3 说明:freopen("123.txt","r",stdin); 适用场景:计数问题、排列组合求值(含模运算)
C++ 36 行 CPP
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3;
int n,m,P,T,jc[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int mi(Re x,Re k){
	Re s=1;
	while(k){
		if(k&1)s=(LL)s*x%P;
		x=(LL)x*x%P,k>>=1;
	}
	return s;
}
inline int inv(Re x){return mi(x,P-2);}
inline int C(Re m,Re n){
	return m>n?0:(LL)jc[n]*inv(jc[m])%P*inv(jc[n-m])%P;
}
inline int Lucas(Re m,Re n){
	return m==0?1:(LL)Lucas(m/P,n/P)*C(m%P,n%P)%P;
}
int main(){
//	freopen("123.txt","r",stdin);
	in(T);
	while(T--){
		in(n),in(m),in(P),jc[0]=1;
		for(Re i=1;i<=P-1;++i)jc[i]=(LL)jc[i-1]*i%P;
		printf("%d\n",Lucas(n,n+m));
	}
}
康托展开 optimize
21 行
CPP JSON
【康托展开】 组合数学与计数模板。 核心函数: void add(int x) — 加法更新 int ask(int x) — 核心算法函数 关键配置: N=1e6+5,P=998244353 适用场景:计数问题、排列组合求值(含模运算)
C++ 20 行 CPP
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<cstdio>
#define LL long long
const int N=1e6+5,P=998244353;
int n,i,ans,a[N],g[N],C[N],jc[N]={1};
inline void add(int x){while(x<=n)++C[x],x+=x&-x;}
inline int ask(int x){
	int ans=0;
	while(x)ans+=C[x],x-=x&-x;
	return ans;
}
int main(){
	scanf("%d",&n);
	for(i=1;i<=n;++i)scanf("%d",&a[i]);
	for(i=n;i;--i)g[i]=ask(a[i]-1),add(a[i]);
	for(i=1;i<=n;++i)jc[i]=(LL)jc[i-1]*i%P;
	for(i=1;i<=n;++i)(ans+=(LL)g[i]*jc[n-i]%P)%=P;
	printf("%d",ans+1);
}
球盒模型全套 Cat
61 行
CPP JSON
【球盒模型全套(Cat)】 组合数学与计数模板。 核心函数: void in(Re &x) — 核心算法函数 LL mi(Re x,Re k) — 核心算法函数 LL niv(Re x) — 核心算法函数 LL c(Re m,Re n) — 核心算法函数 void Stirling(无参数) — 核心算法函数 void DP(无参数) — 核心算法函数 LL Catalan(Re n) — 核心算法函数 说明:freopen("cat.in","r",stdin);;freopen("cat.out","w",stdout); 适用场景:计数问题、排列组合求值(含模运算)
C++ 60 行 CPP
#include<cstdio>
#define LL long long
#define Re register LL
const int P=998244353,N=1e6+5;
LL T,a,b,f,opt,cnt,jc[N*2+5],dp[205][205],S[105][105];
inline void in(Re &x){
    x=f=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f)x=-x;
}
inline LL mi(Re x,Re k){
    Re ans=1;
    while(k){
        if(k&1)ans=(ans*x)%P;
        x=(x*x)%P;k>>=1;
    }
    return ans%P;
} 
inline LL niv(Re x){return mi(x,P-2);}
inline LL c(Re m,Re n){
    if(n<m)return 0;
    if(n<P)return jc[n]*niv(jc[m])%P*niv(jc[n-m])%P;
    return c(m/P,n/P)*c(m%P,n%P)%P;
}
inline void Stirling(){
    for(Re i=0;i<=100;++i)S[i][i]=1;
    for(Re i=1;i<=100;++i)
        for(Re j=1;j<=100;++j)
            S[i][j]=(S[i-1][j-1]+S[i-1][j]*j%P)%P;
}
inline void DP(){
    dp[0][0]=1;
    for(Re i=1;i<=200;++i)
        for(Re j=1;j<=i;++j)
            dp[i][j]=(dp[i-j][j]+dp[i-1][j-1])%P;
}
inline LL Catalan(Re n){return c(n,n<<1)*niv(n+1)%P;}
int main(){
//  freopen("cat.in","r",stdin);
//  freopen("cat.out","w",stdout);
    jc[0]=1;for(Re i=1;i<=N*2;i++)jc[i]=jc[i-1]*i%P;
    in(T);Stirling();DP();
    while(T--){
        in(opt),in(a),in(b);
        if(opt==1)printf("%lld\n",mi(b,a));
        else if(opt==2)printf("%lld\n",c(b-1,a-1));
        else if(opt==3)printf("%lld\n",c(b-1,a+b-1));
        else if(opt==4)printf("%lld\n",S[a][b]);
        else if(opt==5)printf("%lld\n",jc[b]*S[a][b]%P);
        else if(opt==6){
            Re ans=0;
            for(Re i=1;i<=b;++i)(ans+=S[a][i])%=P;
            printf("%lld\n",ans);
        }
        else if(opt==7)printf("%lld\n",dp[a+b][b]);
        else if(opt==8)printf("%lld\n",dp[a][b]);
        else if(opt==9)printf("%lld\n",Catalan(a));
    }
}
第一类斯特林数 n^2递推
14 行
CPP JSON
【第一类斯特林数(n^2递推)】 斯特林数(Stirling Number)模板,划分子集/排列的计数。 核心函数: void get_stiring(Re N) — 获取值 关键配置: N=1003,P=998244353 适用场景:计数问题、排列组合求值(含模运算)
C++ 13 行 CPP
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1003,P=998244353;
int s[N][N]; 
inline void get_stiring(Re N){
	for(Re i=0;i<=N;++i)s[i][i]=1;
	for(Re i=1;i<=N;++i)
		for(Re j=1;j<i;++j)
			s[j][i]=s[j-1][i-1]+(LL)(i-1)*s[j][i-1]%P;
}
int main(){}
第一类斯特林数·行 nlogn 优化倍增 NTT
75 行
CPP JSON
【第一类斯特林数·行(nlogn 优化倍增 NTT)】 斯特林数(Stirling Number)模板,划分子集/排列的计数。 核心函数: void in(Re &x) — 核心算法函数 int mi(Re x,Re k) — 核心算法函数 int inv(Re x) — 求模逆元 void NTT(Re *f,Re n,Re op) — 数论变换 void times(Re *f,Re n,Re *g,Re m) — 核心算法函数 void xplus(Re *f,Re *F,Re n,Re c) — 核心算法函数 void sakura(Re *f,Re n) — 后缀数组 void get_Stirling(Re n) — 获取值 关键配置: N=262144+3,P=167772161,G=3 说明:freopen("123.txt","r",stdin); 适用场景:计数问题、排列组合求值(含模运算)
C++ 74 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LD double
#define LL long long
#define Re register int
using namespace std;
const int N=262144+3,P=167772161,G=3;
int n,m,invn,invG,f[N],g[N],h[N],p[N],tr[N],jc[N],invjc[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int mi(Re x,Re k){
	Re s=1;
	while(k){
		if(k&1)s=(LL)s*x%P;
		x=(LL)x*x%P,k>>=1;
	}
	return s;
}
inline int inv(Re x){return mi(x,P-2);}
inline void NTT(Re *f,Re n,Re op){
	for(Re i=0;i<n;++i)if(i<tr[i])swap(f[i],f[tr[i]]);
	for(Re p=2;p<=n;p<<=1)
		for(Re st=0,len=p>>1,w1=mi(op?invG:G,(P-1)/p);st<n;st+=p)
			for(Re i=st,base=1;i<=st+len-1;++i){
				Re tmp=(LL)base*f[i+len]%P;
				f[i+len]=(f[i]-tmp+P)%P,f[i]=(f[i]+tmp)%P,base=(LL)base*w1%P;
			}
}
inline void times(Re *f,Re n,Re *g,Re m){
	Re n_=n,m_=m;
	for(m+=n,n=1;n<=m;n<<=1);
	for(Re i=n_+1;i<=n;++i)f[i]=0;
	for(Re i=m_+1;i<=n;++i)g[i]=0;
	for(Re i=1;i<n;++i)tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
	NTT(f,n,0),NTT(g,n,0);
	for(Re i=0;i<n;++i)f[i]=(LL)f[i]*g[i]%P;
	NTT(f,n,1);
	for(Re i=0,invn=inv(n);i<=m;++i)f[i]=(LL)f[i]*invn%P;
}
inline void xplus(Re *f,Re *F,Re n,Re c){
	for(Re i=0;i<=n;++i)h[i]=(LL)F[i]*jc[i]%P;
	for(Re i=0,Mi=1;i<=n;++i)p[n-i]=(LL)Mi*invjc[i]%P,Mi=(LL)Mi*c%P;
	times(h,n,p,n);
	for(Re i=0;i<=n;++i)f[i]=(LL)h[n+i]*invjc[i]%P;
}
inline void sakura(Re *f,Re n){
	if(n==1){f[0]=0,f[1]=1;return;}//(x+0)
	if(n&1){
		sakura(f,n-1);
		for(Re i=n;i;--i)f[i]=((LL)f[i]*(n-1)%P+f[i-1])%P;
		f[0]=(LL)f[0]*(n-1)%P;
	}
	else sakura(f,n>>1),xplus(g,f,n>>1,n>>1),times(f,n>>1,g,n>>1);
}
int s[N];
inline void get_Stirling(Re n){
	invjc[1]=invjc[0]=jc[0]=1,invG=inv(G);
	if(n==0){s[0]=1;return;}
	for(Re i=1;i<=n;++i)jc[i]=(LL)jc[i-1]*i%P;
	for(Re i=2;i<=n;++i)invjc[i]=(LL)invjc[P%i]*(P-P/i)%P;
	for(Re i=2;i<=n;++i)invjc[i]=(LL)invjc[i]*invjc[i-1]%P;
	sakura(s,n);
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),get_Stirling(n);
	for(Re i=0;i<=n;++i)printf("%d ",s[i]);
}
第一类斯特林数·行 nlog^2n 暴力分治 NTT
64 行
CPP JSON
【第一类斯特林数·行(nlog^2n 暴力分治 NTT)】 斯特林数(Stirling Number)模板,划分子集/排列的计数。 核心函数: void in(Re &x) — 核心算法函数 int mi(Re x,Re k) — 核心算法函数 int inv(Re x) — 求模逆元 void NTT(Re *f,Re n,Re op) — 数论变换 void times(Re *f,Re n,Re *g,Re m) — 核心算法函数 void CDQ(Re L,Re R,Re deep) — 核心算法函数 void get_Stirling(Re n) — 获取值 关键配置: N=262144+3,P=167772161,G=3 说明:freopen("123.txt","r",stdin); 适用场景:计数问题、排列组合求值(含模运算)
C++ 63 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LD double
#define LL long long
#define Re register int
using namespace std;
const int N=262144+3,P=167772161,G=3;
int n,m,invn,invG,tr[N],A[20][N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int mi(Re x,Re k){
	Re s=1;
	while(k){
		if(k&1)s=(LL)s*x%P;
		x=(LL)x*x%P,k>>=1;
	}
	return s;
}
inline int inv(Re x){return mi(x,P-2);}
inline void NTT(Re *f,Re n,Re op){
	for(Re i=0;i<n;++i)if(i<tr[i])swap(f[i],f[tr[i]]);
	for(Re p=2;p<=n;p<<=1)
		for(Re st=0,len=p>>1,w1=mi(op?invG:G,(P-1)/p);st<n;st+=p)
			for(Re i=st,base=1;i<=st+len-1;++i){
				Re tmp=(LL)base*f[i+len]%P;
				f[i+len]=(f[i]-tmp+P)%P,f[i]=(f[i]+tmp)%P,base=(LL)base*w1%P;
			}
}
inline void times(Re *f,Re n,Re *g,Re m){
	Re n_=n,m_=m;
	for(m+=n,n=1;n<=m;n<<=1);
	for(Re i=n_+1;i<=n;++i)f[i]=0;
	for(Re i=m_+1;i<=n;++i)g[i]=0;
	for(Re i=1;i<n;++i)tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
	NTT(f,n,0),NTT(g,n,0);
	for(Re i=0;i<n;++i)f[i]=(LL)f[i]*g[i]%P;
	NTT(f,n,1);
	for(Re i=0,invn=inv(n);i<=m;++i)f[i]=(LL)f[i]*invn%P;
}
inline void CDQ(Re L,Re R,Re deep){
	if(L==R){A[deep][0]=L,A[deep][1]=1;return;}
	Re mid=L+R>>1;
	CDQ(L,mid,deep+1);
	for(Re i=0;i<=mid-L+1;++i)A[deep][i]=A[deep+1][i];
	CDQ(mid+1,R,deep+1);
	times(A[deep],mid-L+1,A[deep+1],R-mid);
}
int s[N];
inline void get_Stirling(Re n){
	invG=inv(G),CDQ(0,n-1,0);
	for(Re i=0;i<=n;++i)s[i]=A[0][i];
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),get_Stirling(n);
	for(Re i=0;i<=n;++i)printf("%d ",s[i]);
}
第二类斯特林数 n^2递推
14 行
CPP JSON
【第二类斯特林数(n^2递推)】 斯特林数(Stirling Number)模板,划分子集/排列的计数。 核心函数: void get_Stiring(Re N) — 获取值 关键配置: N=1003,P=998244353 适用场景:计数问题、排列组合求值(含模运算)
C++ 13 行 CPP
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1003,P=998244353;
int S[N][N]; 
inline void get_Stiring(Re N){
	for(Re i=0;i<=N;++i)S[i][i]=1;
	for(Re i=1;i<=N;++i)
		for(Re j=1;j<i;++j)
			S[j][i]=S[j-1][i-1]+(LL)j*S[j][i-1]%P;
}
int main(){}
第二类斯特林数·行 NTT
54 行
CPP JSON
【第二类斯特林数·行(NTT)】 斯特林数(Stirling Number)模板,划分子集/排列的计数。 核心函数: void in(Re &x) — 核心算法函数 int mi(Re x,Re k) — 核心算法函数 int inv(Re x) — 求模逆元 void NTT(Re *f,Re n,Re op) — 数论变换 void sakura(Re *f,Re n,Re *g,Re m) — 后缀数组 void get_Stirling(Re n) — 获取值 关键配置: N=524288+3,P=167772161,G=3 说明:freopen("123.txt","r",stdin); 适用场景:计数问题、排列组合求值(含模运算)
C++ 53 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=524288+3,P=167772161,G=3;
int n,invG,f[N],g[N],tr[N],jc[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int mi(Re x,Re k){
	Re s=1;
	while(k){
		if(k&1)s=(LL)s*x%P;
		x=(LL)x*x%P,k>>=1;
	}
	return s;
}
inline int inv(Re x){return mi(x,P-2);}
inline void NTT(Re *f,Re n,Re op){
	for(Re i=0;i<n;++i)if(i<tr[i])swap(f[i],f[tr[i]]);
	for(Re p=2;p<=n;p<<=1)
		for(Re st=0,len=p>>1,w1=mi(op?invG:G,(P-1)/p);st<n;st+=p)
			for(Re i=st,base=1;i<=st+len-1;++i){
				Re tmp=(LL)f[i+len]*base%P;
				f[i+len]=(f[i]-tmp+P)%P,(f[i]+=tmp)%=P,base=(LL)base*w1%P;
			}
}
inline void sakura(Re *f,Re n,Re *g,Re m){
	for(m+=n,n=1;n<=m;n<<=1);
	for(Re i=1;i<n;++i)tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
	NTT(f,n,0),NTT(g,n,0);
	for(Re i=0;i<n;++i)f[i]=(LL)f[i]*g[i]%P;
	NTT(f,n,1);
	for(Re i=0,invn=inv(n);i<=m;++i)f[i]=(LL)f[i]*invn%P;
}
int S[N];
inline void get_Stirling(Re n){
	jc[0]=1,invG=inv(G);
	for(Re i=1;i<=n;++i)jc[i]=(LL)jc[i-1]*i%P;
	for(Re i=0;i<=n;++i)f[i]=(LL)inv(jc[i])*((i&1)?P-1:1)%P,g[i]=(LL)mi(i,n)*inv(jc[i])%P;
	sakura(f,n,g,n);
	for(Re i=0;i<=n;++i)S[i]=f[i];
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),get_Stirling(n);
	for(Re i=0;i<=n;++i)printf("%d ",S[i]);
}
组合数 n^2记搜
13 行
CPP JSON
【组合数(n^2记搜)】 组合数学与计数模板。 核心函数: int C(Re m,Re n) — 核心算法函数 关键配置: N=1003,P=998244353 适用场景:计数问题、排列组合求值(含模运算)
C++ 12 行 CPP
#include<cstdio>
#define Re register int
using namespace std;
const int N=1003,P=998244353;
int C_[N][N]; 
inline int C(Re m,Re n){
    if(m>n)return 0;
    if(!m||m==n)return C_[m][n]=1;
    if(C_[m][n])return C_[m][n];
    return C_[m][n]=(C(m,n-1)+C(m-1,n-1))%P;
}
int main(){}
组合数 n^2递推
14 行
CPP JSON
【组合数(n^2递推)】 组合数学与计数模板。 核心函数: void get_C(Re N) — 获取值 关键配置: N=1003,P=998244353 适用场景:计数问题、排列组合求值(含模运算)
C++ 13 行 CPP
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1003,P=998244353;
int C[N][N];
inline void get_C(Re N){
	for(Re i=0;i<=N;++i)C[0][i]=C[i][i]=1;
	for(Re i=1;i<=N;++i)
		for(Re j=1;j<i;++j)
			C[j][i]=(C[j-1][i-1]+C[j][i-1])%P;
}
int main(){}
贝尔数Bell n^2递推
32 行
CPP JSON
【贝尔数Bell(n^2递推)】 组合数学与计数模板。 核心函数: void get_C(Re N) — 获取值 void get_Bell(Re N) — 获取值 void get_Stiring(Re N) — 获取值 void get_Bell_(Re N) — 获取值 关键配置: N=1003,P=998244353 适用场景:计数问题、排列组合求值(含模运算)
C++ 31 行 CPP
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1003,P=998244353;
int B[N],C[N][N],S[N][N];
inline void get_C(Re N){
	for(Re i=0;i<=N;++i)C[0][i]=C[i][i]=1;
	for(Re i=1;i<=N;++i)
		for(Re j=1;j<i;++j)
			C[j][i]=(C[j-1][i-1]+C[j][i-1])%P;
}
inline void get_Bell(Re N){
	B[0]=1,get_C(N);
	for(Re i=1;i<=N;++i)
		for(Re j=0;j<=i-1;++j)
			(B[i]+=(LL)C[j][i-1]*B[j]%P)%=P;
}
inline void get_Stiring(Re N){
	for(Re i=0;i<=N;++i)S[i][i]=1;
	for(Re i=1;i<=N;++i)
		for(Re j=1;j<i;++j)
			S[j][i]=S[j-1][i-1]+(LL)j*S[j][i-1]%P;
}
inline void get_Bell_(Re N){
	B[0]=1,get_Stiring(N);
	for(Re i=1;i<=N;++i)
		for(Re j=1;j<=i;++j)
			(B[i]+=S[j][i])%=P;
}
int main(){}
已复制