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;
}