上升幂与下降幂

• 上升幂：\(x^{\overline{n}}=\prod_{k=0}^{n-1}(x+k)=x(x+1)(x+2)...(x+n-1)\)
• 下降幂：\(x^{\underline{n}}=\frac{x!}{(x-n)!}=\prod_{k=0}^{n-1}(x-k)\)

第一类斯特林数(无符号)

• 定义：第一类斯特林数（斯特林轮换数）\(n\brack k\)，也可记做\(s(n,k)\) ，表示将\(n\)个两两不同的元素，划分为\(k\)个互不区分的非空轮换的方案数。一个轮换就是一个首尾相接的环形排列。我们可以写出一个轮换\([A,B,C,D]\) ，并且我们认为\([A,B,C,D]=[B,C,D,A]=[C,D,A,B]=[D,A,B,C]\) ，即，两个可以通过旋转而互相得到的轮换是等价的。注意，我们不认为两个可以通过翻转而相互得到的轮换等价，即\([A,B,C,D]\neq [D,C,B,A]\) 。(另一种理解：将 \(n\) 个元素，划分为 \(k\) 个圆排列的方案数)

• 递推式：\({n\brack k}={n-1\brack k-1}+(n-1){n-1 \brack k}\)。边界\({n\brack 0}=[n=0]\)

  组合意义：将该新元素置于一个单独的轮换中，共有\({n-1\brack k-1}\)中方案；将该元素插入到任何一个现有的轮换中，共有\((n-1){n-1 \brack k}\)种方案。

• 性质

  \(\sum_{k=0}^n{n\brack k}=n!\)

  \({n\brack n-1}=\binom{n}{2}\)

  \({n\brack 2}=(n-1)!\sum_{i=1}^{n-1}\frac{1}{i}\)

  \({n\brack 1}=(n-1)!\)

生成函数(同行) 上升幂：\(F_n(x)=x^{\overline{n}}=\prod_{i=0}^{n-1}(x+i)=\frac{(x+n-1)!}{(x-1)!}=\prod_{i=0}^n{n\brack i}x^i\)
\(O(nlogn)\)

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    //freopen("gen.in","r",stdin);
    Poly::init(19);
    auto CDQ=[&](auto self,int l,int r)->Poly::poly{
        if(l==r) return Poly::poly({l,1});
        int mid=l+r>>1;
        return Poly::poly_mul(self(self,l,mid),self(self,mid+1,r));
    };
    int n;
    cin>>n;
    Poly::poly F=CDQ(CDQ,0,n-1);
    for(int i=0;i<=n;i++) cout<<F[i]<<" ";
    return 0;
}

生成函数(同列)：\(F(x)=\sum_{i=1}^n\frac{(i-1)!x^i}{i!}=\sum_{i=1}^n\frac{x^i}{i}=\sum_{i=1}^n{i \brack k}x^i\)

第二类斯特林数(无符号)

• 定义：第二类斯特林数（斯特林子集数）\(n \brace k\)，也可记做\(S(n,k)\) ，表示将\(n\)个两两不同的元素，划分为\(k\) 个互不区分的非空子集的方案数

• 递推式：\({n\brace k}={n-1\brace k-1}+k{n-1\brace k}\)

  组合意义：插入一个新元素时，可以将这个元素单独放入一个子集，也可以将这个元素放入现有的一个非空子集

• 通项公式：\({n\brace m}=\sum_{i=0}^m\frac{(-1)^{m-i}i^n}{i!(m-i)!}\)

• 性质

  \(\sum_{k=0}^n{n\brace k}=B_n\)，\(B_n\)为贝尔数

  \(n^k=\sum_{i=1}^k{k\brace i}\times i!\times \binom{n}{i}=\sum_{i=1}^k{k\brace i}\times n^{\underline{i}}\)，这个可以用来求自然数数幂和：\(\sum_{i=1}^n i^k=\sum_{i=1}^n\sum_{j=0}^k{k\brace j}\times j!\times \binom{i}{j}=\sum_{j=0}^k{k\brace j}\times j!\sum_{i=1}^n\binom{i}{j}=\sum_{j=0}^k{k\brace j}\times j!\times \binom{n+1}{j+1}=\sum_{j=0}^k{k\brace j}\frac{(n+1)^{\underline{j+1}}}{(j+1)!}\)

• 同一行第二类斯特林数通项公式计算\(O(nlogn)\)

int main() {
    scanf("%d", &n);
    poly f(n + 1), g(n + 1);
    for (int i = 0; i <= n; ++i)
        g[i] = (i & 1 ? mod - 1ll : 1ll) * infac[i] % mod,
        f[i] = 1ll * qpow(i, n) * infac[i] % mod;
    poly F=poly_mul(f,g);
    F.resize(n + 1);
    for (int i = 0; i <= n; ++i)
        printf("%d ", F[i]);
    return 0;
}

分拆数

• 定义：将正整数\(n\)进行整数拆分的方案数

• 求法：

  • 完全背包，把数字\(1-n\)看做价值为\(1\)，容量为\(i\)的物品，进行完全背包
  • 五边形定理

    #include <stdio.h>
    
    long long a[100010];
    long long p[50005];
    
    int main() {
    p[0] = 1;
    p[1] = 1;
    p[2] = 2;
    int i;
    for (i = 1; i < 50005;i++) /*递推式系数1,2,5,7,12,15,22,26...i*(3*i-1)/2,i*(3*i+1)/2*/
    {
        a[2 * i] = i * (i * 3 - 1) / 2; /*五边形数为1,5,12,22...i*(3*i-1)/2*/
        a[2 * i + 1] = i * (i * 3 + 1) / 2;
    }
    for (  i = 3; i < 50005; i++) /*p[n]=p[n-1]+p[n-2]-p[n-5]-p[n-7]+p[12]+p[15]-...+p[n-i*[3i-1]/2]+p[n-i*[3i+1]/2]*/
    {
        p[i] = 0;
        int j;
        for (j = 2; a[j] <= i; j++) /*有可能为负数,式中加1000007*/
        {
        if (j & 2) {
            p[i] = (p[i] + p[i - a[j]] + 1000007) % 1000007;
        } else {
            p[i] = (p[i] - p[i - a[j]] + 1000007) % 1000007;
        }
        }
    }
    int n;
    while (~scanf("%d", &n)) {
        printf("%lld\n", p[n]);
    }
    }
    

• \(k\)个部分的分拆，记作\(p(n,k)\)

  \(p(n,k)=p(n-1,k-1)+p(n-k,k)\)

例题

2021CCPC Guangzhou A

参考：OIWiki