#include <bits/stdc++.h>
#define int long long
using namespace std ;
const int mod = 1e9 + 7 ;
inline int read() {
int x = 0 , f = 1 ;
char c = getchar() ;
while (c < '0' || c > '9') {
if (c == '-') f = -f ;
c = getchar() ;
}
while (c >= '0' && c <= '9') {
x = x * 10 + c - '0' ;
c = getchar() ;
}
return x * f ;
}
int N , M ; int dp[52][52] , g[52][52][52] , f[52] ;
int C[52][52] ;
int Quick_Pow(int a , int b) {
int ans = 1 ;
while (b) {
if (b & 1) ans = (ans * a) % mod ;
a = (a * a) % mod ; b >>= 1 ;
}
return ans ;
}
signed main() {
#ifndef ONLINE_JUDGE
freopen("1.in" , "r" , stdin) ;
freopen("1.out" , "w" , stdout) ;
#endif
N = read() , M = read() ;
C[0][0] = 1 ;
for (int i = 1 ; i <= N ; ++ i) {
C[i][0] = 1 ;
for (int j = 1 ; j <= i ; ++ j) {
C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod ;
}
}
f[1] = 1 ; dp[1][0] = 1 ;
g[1][0][1] = 1 ;
for (int n = 2 ; n <= N ; ++ n) {
f[n] = Quick_Pow(2 , C[n][2]) ;
for (int j = 1 ; j < n ; ++ j)
f[n] = (f[n] + mod - (((C[n - 1][j - 1] * f[j]) % mod) * Quick_Pow(2 , C[n - j][2])) % mod) % mod ;
cerr << f[n] << '\n' ;
for (int k = 1 ; k <= n ; ++ k) {
for (int j = 0 ; j <= n - k ; ++ j) {
for (int i = 1 ; i <= n - k + 1 ; ++ i) {
for (int x = 0 ; x <= min(j , i - 1) ; ++ x) {
g[n][j][k] = (g[n][j][k] + ((C[n - 1][i - 1] * dp[i][x]) % mod) * (g[n - i][j - x][k - 1] * i) % mod) % mod ;
}
}
}
}
for (int j = 1 ; j <= n - 1 ; ++ j) {
for (int i = 1 ; i <= n - j ; ++ i) {
for (int x = 1 ; x <= j ; ++ x) {
dp[n][j] = (dp[n][j] + (((dp[i][0] * g[n - i][j - x][x]) % mod) * Quick_Pow(i , x)) % mod) % mod ;
}
}
}
dp[n][0] = f[n] ;
for (int j = 1 ; j <= n - 1 ; ++ j) {
dp[n][0] = (dp[n][0] + mod - dp[n][j]) % mod ;
}
cerr << '\n' ;
}
int ans = 0 ;
for (int j = 1 ; j <= M ; ++ j) {
ans = (ans + dp[N][j]) % mod ;
}
printf("%lld" , ans) ;
}
标签:int,many,long,How,read,getchar
From: https://www.cnblogs.com/hangry/p/18285436