三只小猪

https://www.luogu.org/problemnew/show/P3904

C++版本一

题解：高精度
参考文章：https://blog.csdn.net/weixin_43272781/article/details/86528384

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
using namespace std;
typedef long long ll;
typedef __int128 lll;
const int N=100+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,q;
int ans,cnt,flag,temp;
int a[N][N][200];
int tmp[200];
void times(int b[],int x){
    for(int i=1;i<=b[0];i++){
        tmp[i]=b[i]*x;
    }
    for(int i=1;i<=b[0]+100;i++){
        if(tmp[i]>=10){
            tmp[i+1]+=tmp[i]/10;
            tmp[i]%=10;
        }
        if(tmp[i]){
            tmp[0]=max(tmp[0],i);
        }
    }

}
void add (int b[],int c[]){
    int x=max(b[0],c[0]);
    for(int i=1;i<=x;i++){
        b[i]=b[i]+c[i];
    }
    for(int i=1;i<=x+100;i++){
        if(b[i]>=10){
            b[i+1]+=b[i]/10;
            b[i]%=10;
        }
        if(b[i]){
            b[0]=max(b[0],i);
        }
    }

}
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //scanf("%d",&n);
    //scanf("%d",&t);
    for(int i=1;i<=50;i++){
        a[i][1][1]=a[i][i][1]=a[i][1][0]=a[i][i][0]=1;
        for(int j=2;j<i;j++){
            memset(tmp,0,sizeof(tmp));
            times(a[i-1][j],j);
            add(tmp,a[i-1][j-1]);
            memcpy(a[i][j],tmp,sizeof(a[i][j]));
            //a[i][j]=a[i-1][j]*j+a[i-1][j-1];
//            for(int k=a[i][j][0];k>=1;k--){
//                printf("%d",a[i][j][k]);
//            }
//            printf("\n");
        }
    }
    while(~scanf("%d%d",&n,&m)){
        if(n<m){
            printf("0\n");
            continue;
        }
        for(int i=a[n][m][0];i>=1;i--){
            printf("%d",a[n][m][i]);
        }
        printf("\n");
    }


    //cout << "Hello world!" << endl;
    return 0;
}

C++版本二

#include<cstdio>
#include<iostream>
using namespace std;
long long a[55][55][1010];
int n;
int m;
void add(int u,int v){
    for(int i=1;i<=max(a[u-1][v-1][0],a[u-1][v][0]);i++){
        a[u][v][i]+=a[u-1][v-1][i];
        a[u][v][i]+=v*a[u-1][v][i];
    }
    a[u][v][0]=max(a[u-1][v-1][0],a[u-1][v][0]);
    for(int i=1;i<=a[u][v][0];i++){
        a[u][v][i+1]+=a[u][v][i]/10;
        a[u][v][i]%=10;
    }
    while(a[u][v][a[u][v][0]+1]){
        a[u][v][0]++;
        a[u][v][a[u][v][0]+1]+=a[u][v][a[u][v][0]]/10;
        a[u][v][a[u][v][0]]%=10;
    }
}
int main(){
    a[1][1][0]=1;
    a[1][1][1]=1;
    cin>>n>>m;
    for(int i=2;i<=n;i++){
        for(int j=1;j<=i;j++){
            add(i,j);
        }
    }
    if(a[n][m][0]==0){
        cout<<"0"<<endl;
        return 0;
    }
    for(int i=a[n][m][0];i>=1;i--){
        cout<<a[n][m][i];
    }
    return 0;
}

Python版本一

def work(n, m):
    f = [[0 for i in range(300)] for i in range(300)]
    for i in range (1, n + 1):
        f[i][1] = 1
        for j in range (2, m + 1):
            f[i][j] = f[i - 1][j - 1] + j * f[i - 1][j]
    return f[n][m]

def main():
    s = input().split()
    print(work(int(s[0]), int(s[1])))
main()