题解 P2028 【龙兄摘苹果】

· · 题解

题意简述

把 n 个元素分成 k 个非空集合的方案数（集合内无序），即 S(n,k) 。

推导过程

  1. 如果前 n-1 个元素组成了 k-1 个非空集合，那么第 n 个元素自然成为第 k 个非空集合。
  2. 如果前 n-1 个元素组成了 k 个非空集合，那么第 n 个元素可以放进这 k 个非空集合中的任意一个。

递推式

由推导过程可以得出递推式，S(i,j) = S(i-1,j-1) + S(i-1,j)*j 。

需要注意的是，由于数据范围很大，除了要开 unsigned long long ，递推的过程中还必须时刻取模！！！

Code:

#include<bits/stdc++.h>
using namespace std;
unsigned long long f[10005][1005];
long long n,k,p;
int main()
{
    cin>>n>>k>>p;
    f[1][1] = 1;
    for(int i=1;i<=n;i++)  //为了省略重置 S(1,j) 的循环步骤
    {
        f[i][1] = 1;     //无论多少个元素，当要组成1个集合时，只有一种办法 
        for(int j=1;j<=k;j++)
        {
            f[i][j] = (f[i-1][j-1]%p + (f[i-1][j]%p)*(j%p))%p;   //递推式，注意取模 
            f[1][1] = 1;   //填坑 
        }
    }
    cout<<f[n][k];  //输出
    return 0;
}