这题71tle很正常，时间限制有问题本来是4秒的

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e2+10;
int n,mod;
int C[N][N];//组合数
int power[N*N];//2的幂次,最大需要 n*(n-1)/2≈125000
int dp[N][N];// dp[i][j]: 已处理i个点，当前层j个点
int mypow(int a,int b){
	int res=1;
	while(b){
		if(b&1)	res=(res*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return res;
}
void initC(){
    for(int i=0;i<=n;i++){
		C[i][0]=C[i][i]=1;
		for(int j=1;j<i;j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
	}
}
int ans=0;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>mod;
	initC();
	int maxn=n*n;
	power[0]=1;
	for(int i=1;i<=maxn;i++)	power[i]=power[i-1]*2%mod;
	dp[1][1]=1;
	for(int i=2;i<=n-1;i++){
		for(int j=1;j<i;j++){
			for(int k=1;k<=(i-j);k++){
				if(!dp[i-j][k]) continue;
				int way=C[n-1-(i-j)][j]%mod;
				way=(way*power[(j*(j-1))/2])%mod;
				way=way*mypow((power[k]-1),j)%mod;
				way%=mod;
				way+=mod;
				way%=mod;
				dp[i][j]+=dp[i-j][k]*way;
				dp[i][j]%=mod;
			}
		}
	}
	for(int i=1;i<=n-1;i++){
		ans+=dp[n-1][i]*(power[i]-1+mod)%mod;
		ans%=mod;
	}
	cout<<ans;
    return 0;
}
/*
深度思考
我们把n个节点分成多层
第一层是1最后一层是N
我们对于每层假设当前层有j个节点
这j个节点对上一层k个节点
那么当前层与上一层的方案数是(2^k-1)^j
2^k上层k个节点每个节点连于不连
-1是去掉全部不连的
j次方是有j个
当前层的节点互相连的方案数是2^(j*(j-1)/2)
(j*(j-1)/2)是所有边的个数2是判断是否保留
不用减1可以都不连
但是我们不能定义dp[i][j][k]表示这一层,当前节点数,上一层节点数
这样不确定
所以我们定义dp[i][j]表示已经处理了i个点当前层是j个点
我们枚举k
dp[i][j]<-dp[i-j][k]*C(j,n-1(i-j))*2^(j(j-1)/2)*(2^k-1)^j
ans=sum(1,n)dp[n-1][i]*(2^i-1)^1
也就是
ans=sum(1,n)dp[n-1][i]*(2^i-1)
*/