[luogu1655][小朋友的球]

<a href="https://www.luogu.org/problemnew/show/P1655"target="_blank">luogu1665

思路

一道第二类斯特兰数的模板题。只不过需要写个高精。

f[i][j]表示前i个球放到j个盒子里的方案数。第i个球可以单独一个盒子，所以f[i][j]+=f[i-1][j-1]。还可以与前面的放到同一个盒子里，所以f[i][j]+=f[i-1][j]*j

代码

#include<cstring>

#include<cstdio>

#include<iostream>

using namespace std;

struct BIGNUM {

	int n,a[1000];

	BIGNUM() {

		n=0;

		memset(a,0,sizeof(a));

	}

	BIGNUM(int x) {

		n=0;

		memset(a,0,sizeof(a));

		while(x) {

			a[++n]=x%10;

			x/=10;

		}

	}

	BIGNUM operator * (int x) const{

		BIGNUM c(0);

		c.n=n;

		for(int i=1;i<=c.n;++i)

			c.a[i]=a[i]*x;

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

			if(c.a[i]>=10) {

				c.a[i+1]+=c.a[i]/10;

				c.a[i]%=10;

				if(c.n==i) c.n++;

			}

		}

		return c;

	}

	BIGNUM operator + (const BIGNUM &x) const {

		BIGNUM c(0);

		c.n=max(x.n,n);

		for(int i=1;i<=c.n;++i)

			c.a[i]=x.a[i]+a[i];

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

			if(c.a[i]>=10) {

				c.a[i+1]+=c.a[i]/10;

				c.a[i]%=10;

				if(i==c.n) ++c.n;

			}

		}

		return c;

	}

	void print() {

		for(int i=n;i>=1;--i) printf("%d",a[i]);

		if(n==0)

		puts("0");

		else puts("");

	}

}f[101];

int main() {

	int n,m;

	while(scanf("%d%d",&n,&m)!=EOF) {

		f[1]=BIGNUM(1);

		f[0]=BIGNUM(0);

		for(int i=2;i<=m;++i) f[i]=BIGNUM(0);

		for(int i=2;i<=n;++i)

			for(int j=m;j>=1;--j)

				f[j]=f[j-1]+f[j]*j;

		f[m].print();

	}

	return 0;

}