C++(g++ 7.5.0) 解法, 执行用时: 3ms, 内存消耗: 1164K, 提交时间: 2023-06-13 16:24:26

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int p=1e9+7;
int n,m,ans,f[305][305];
signed main()
{
    scanf("%lld%lld",&n,&m);
    f[0][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)f[i][j]=(f[i-1][j]+f[i-1][j-1]*(m-j+1)%p)%p;
    for(int i=1;i<=m;i++)ans=(ans+f[n][i])%p;
    cout<<ans;
}

C++14(g++5.4) 解法, 执行用时: 6ms, 内存消耗: 1136K, 提交时间: 2019-10-20 10:07:12

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k;
int f[303][303];
const int mod=1e9+7;
main() {
    cin>>n>>k;
    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]+f[i-1][j-1]*(k-j+1))%mod;
    int ans=0;
    for(int i=1;i<=k;i++) {
        ans+=f[n][i];
        ans%=mod;
    }
    cout<<ans;  
}

Python3 解法, 执行用时: 79ms, 内存消耗: 6876K, 提交时间: 2021-05-27 14:06:23

MOD = int(1e9 + 7)

n, k = map(int, input().split())
for _ in range(n - 1):
    u, v = map(int, input().split())

f = [[0] * (k + 1) for _ in range(n + 1)]
f[0][0] = 1
for i in range(1, n + 1):
    for j in range(1, k + 1):
        f[i][j] = (f[i - 1][j] + f[i - 1][j - 1] * (k - j + 1)) % MOD
print(sum(f[-1]) % MOD)

C++11(clang++ 3.9) 解法, 执行用时: 6ms, 内存消耗: 1248K, 提交时间: 2020-04-18 16:48:24

#include<iostream>
using namespace std;
#define L long long
const L M=1e9+7;
L n,m,ans,f[303][303];
int main(){
    cin>>n>>m;
    f[0][0]=1;
    for(L i=1;i<=n;i++)
        for(L j=1;j<=m;j++) f[i][j]=(f[i-1][j]+f[i-1][j-1]*(m-j+1)%M)%M;
    for(L i=1;i<=m;i++) ans=(ans+f[n][i])%M;
    cout<<ans;
}