已备案网站域名网,合肥城市建设网站,有域名就可以做网站吗,网站开发实训报告参考文献题目 思路来源
灵茶山群群友
https://blog.csdn.net/Code92007/article/details/110354429
题解 其实想了想#xff0c;和20年小米邀请赛决赛这个G题的dp思路是一样的#xff0c;姑且称为sg图dp吧
按sg值从大到小dp#xff0c;每次补上全局sg值-1的这些点#xff0c;
…题目 思路来源
灵茶山群群友
https://blog.csdn.net/Code92007/article/details/110354429
题解 其实想了想和20年小米邀请赛决赛这个G题的dp思路是一样的姑且称为sg图dp吧
按sg值从大到小dp每次补上全局sg值-1的这些点
本题就是先预处理f[i][j]表示i个点与j个点里至少一个点联通
然后每次把j个点作为一个新sg值加进去
感觉没想到就怎么都想不到想到了就能秒了
代码
//#includebits/stdc.h
#includeiostream
#includecstdio
#includevector
#includemap
#includequeue
#includeset
using namespace std;
#define rep(i,a,b) for(int i(a);i(b);i)
#define per(i,a,b) for(int i(a);i(b);--i)
typedef long long ll;
typedef double db;
typedef pairint,int P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr(#x):x ;
#define dbg2(x) cerr(#x):xendl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf(%d,(a))
#define pt(a) printf(%d,a);
#define pte(a) printf(%d\n,a)
#define ptlle(a) printf(%lld\n,a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
const int N5e310;
int n,mod,ans,f[N][N],dp[N],bs[N];
//注意到sgx的需要和sgx-1,sgx-2,...,sg0的每个都至少有一条边
//所以按sg值分组背包每次把所有sg值相同的分层加入
//f[i][j]表示i个x的j个x的 i个每个挂了j个中至少1个的方案数
//dp[i]表示i个x的 枚举j个x的挂上去
void add(int x,int y){x(xy)%mod;
}
int main(){sci(n),sci(mod);rep(i,1,n){bs[i](2ll*bs[i-1]1)%mod;//bs[i]2^i-1}f[0][1]1;rep(i,0,n){rep(j,1,n-i-1){add(f[i1][j],1ll*f[i][j]*bs[j]%mod);add(f[i][j1],f[i][j]);}}rep(i,1,n)dp[i]1;rep(i,1,n){rep(j,1,n-i){add(dp[ij],1ll*dp[i]*f[i][j]%mod);}}pte(dp[n]);return 0;
}
