分析

第二类striling数

考虑最后一个数到底是放在之前的任意一个集合内，还是自成一个集合

\[F_{i\ j}=F_{i-1\ j-1}+j\times F_{i-1,j}
\]

AC代码

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long LL;

int n,k;

LL f[10005][1005],p;

inline int read() {

	int w=0,x=0; char ch=0;

	while (!isdigit(ch)) {w|=ch=='-';ch=getchar();}

	while (isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}

	return w?-x:x;

}

int main() {

	n=read(),k=read();

	scanf("%lld",&p);

	f[0][0]=1;

	for (int i=1;i<=n;i++) {

		for (int j=1;j<=k;j++) {

			f[i][j]=((f[i-1][j-1]+p)%p+(j*f[i-1][j]+p)%p+p)%p;

		}

	}

	printf("%llu\n",f[n][k]);

	return 0;

}

巴特西

【洛谷P2028 龙兄摘苹果】动态规划

分析

AC代码

最新文章

热门文章