第一类斯特林数、第二类斯特林数、贝尔数总结+模板

r囧r小猫 2023-06-03 13:52 24阅读 0赞

转载[https://blog.csdn.net/sxh759151483/article/details/83420939][https_blog.csdn.net_sxh759151483_article_details_83420939]

第一类斯特林数  
解决问题：给n个元素，求出k个环排列的方法数  
Stirling\[n\]\[k\]  
1  
1 1  
2 3 1  
6 11 6 1  
24 50 35 10 1  
120 274 225 85 15 1  
720 1764 1624 735 175 21 1  
5040 13068 13132 6769 1960 322 28 1  
40320 109584 118124 67284 22449 4536 546 36 1  
362880 1026576 1172700 723680 269325 63273 9450 870 45 1

const int maxn = 21;
    ll Stirling[maxn][maxn], fac[maxn] = {
        1};
    void init() {
        for(ll i = 1; i < maxn; i++)
            fac[i] = fac[i - 1] * i;
        Stirling[0][0] = 0;
        Stirling[1][1] = 1;
        for(ll i = 2; i < maxn; i++) {
            for(ll j = 1; j <= i; j++) {
                Stirling[i][j] = Stirling[i - 1][j - 1] + (i - 1) * Stirling[i - 1][j];
            }
        }
    }

第二类斯特林数  
将n个不同元素拆分成m个集合的方案数  
Stirling\[n\]\[m\]  
1  
1 1  
1 3 1  
1 7 6 1  
1 15 25 10 1  
1 31 90 65 15 1  
1 63 301 350 140 21 1  
1 127 966 1701 1050 266 28 1  
1 255 3025 7770 6951 2646 462 36 1  
1 511 9330 34105 42525 22827 5880 750 45 1

const int maxn = 21;
    ll Stirling[maxn][maxn];
    void init() {
        Stirling[0][0] = 0;
        Stirling[1][1] = 1;
        for(ll i = 2; i < maxn; i++) {
            for(ll j = 1; j <= i; j++) {
                Stirling[i][j] = Stirling[i - 1][j - 1] + j * Stirling[i - 1][j];
            }
        }
    }

贝尔数  
n个数可以划分成多少个集合  
每个贝尔数是第二类斯特林数的和  
Bell\[n\]

ll Bell[maxn];
    void init() {
        ll x[maxn];
        Bell[0] = 1LL;
        Bell[1] = 1LL;
        x[0] = 1LL;
        for(int i = 2; i < maxn; i++) {
            x[i - 1] = Bell[i - 1];
            for(int j = i - 2; j >= 0; j--)
                x[j] = (x[j]%mod + x[j + 1]%mod)%mod;
            Bell[i] = x[0]%mod;
        }
    }

HDU：2512（贝尔数裸题）

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn=1e4+10;
    const ll mod=1000;
    int n;
    ll Bell[maxn];
    void init() {
        ll x[maxn];
        Bell[0] = 1LL;
        Bell[1] = 1LL;
        x[0] = 1LL;
        for(int i = 2; i < maxn; i++) {
            x[i - 1] = Bell[i - 1];
            for(int j = i - 2; j >= 0; j--)
                x[j] = (x[j]%mod + x[j + 1]%mod)%mod;
            Bell[i] = x[0]%mod;
        }
    }
    int main(){
        int T;
        init();
        while(cin>>T){
            while(T--){
                cin>>n;
                cout<<Bell[n]<<endl;
            }
        }
    
    
    
    
    
        return 0;
    }

转载于:https://www.cnblogs.com/lin1874/p/11405879.html

[https_blog.csdn.net_sxh759151483_article_details_83420939]: https://blog.csdn.net/sxh759151483/article/details/83420939
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/e4662bf6bac8447893750c1785e62a53.png