记录编号	600991	评测结果	AAAAAAAAAA
题目名称	3132.玩具	最终得分	100
用户昵称	wdsjl	是否通过	通过
代码语言	C++	运行时间	0.714 s
提交时间	2025-05-23 10:06:37	内存使用	4.42 MiB

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll mod, n;
ll inv[304], f[304][304], h[304][304], dp[304][304];

int main() {
	freopen("toyy.in","r",stdin);
	freopen("toyy.out","w",stdout); 
    scanf("%lld %lld", &n, &mod);
    inv[0] = inv[1] = 1;
    dp[1][1] = 1;
    
    for (int i = 2; i <= n; i++) {
        inv[i] = (mod - mod/i) * inv[mod%i] % mod;
        (inv[i] += mod) %= mod;
    }
    
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            dp[i][j] = dp[i-1][j-1] * (j-1) % mod * inv[i] % mod + 
                       dp[i-1][j] * (i-j) % mod * inv[i] % mod;
            dp[i][j] %= mod;
        }
    }
    
    for (int i = 0; i <= n; i++)
        h[0][i] = 1;
    
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            if (j) f[i][j] = h[i-1][j-1];
            else f[i][j] = (i < 2);
            
            for (int k = 1; k <= i; k++) {
                h[i][j] = (h[i][j] + f[k][j] * h[i-k][j] % mod * dp[i][k] % mod) % mod;
            }
        }
    }
    
    ll ans = 0;
    for (int i = 1; i < n; i++) {
        ans += (f[n][i] % mod - f[n][i-1] % mod) * i % mod;
        ans %= mod;
    }
    
    return !printf("%lld", (ans + mod) % mod);
}