题解 P2028 【龙兄摘苹果】

VCVCVCFop_zz · 2017-01-13 15:19:26 · 题解

这个。。裸的第二类斯特林数

数学公式为s[i][j]=s[i-1][j-1]+s[i-1][j]*j

思想为：第i个数自成一个集合或者加入别的集合，别的集合有j个所以s[i-1][j]*j

TIP：本题一定要一路取模！！！表示long long都炸了、、最后全加取模同时开unsigned long long

CODE：

#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
unsigned long long f[10001][1001]={0};
int main()
{
    long long n,m,mo;
    cin>>n>>m>>mo;
    f[1][1]=1;
    for (int  i=1;i<=n;i++)
    {
        f[i][1]=1;
        for (int  j=1;j<=m;j++)
            if(i==1&&j==1) continue;else
            f[i][j]=((j%mo)*(f[i-1][j]%mo)%mo+(f[i-1][j-1])%mo)%mo;
    }
    printf("%llu\n",f[n][m]);
}