https://atcoder.jp/contests/abc281/tasks/abc281_g
The desired graphs are equivalent to simple connected undirect graph such that $dis[1]=0,dis[n]=\max,0<dis[i]<\max$
Then consider a bfs tree:
The vertices at the $i$-th level represents $dis=i$, a bfs tree can restore many graphs, just met the following conditions:
- Each vertex has edge with at least one vertex in the previous level
- Edges between vertices at the same level are optional
Let $dp[i][j]$ represents the number of graphs consisting of $i$ vertices and last level has $j$ vertices
$dp[1][1]=1$, $dp[i][j]$ can be transitioned by all $dp[i-j][k]$
Then consider the count in a transition, let $cur$ = the number of vertices in the last level, $last$ = the number of vertices in the penultimate level:
- Each vertex has edge with at least one vertex in the previous level. For each vertex there are $2^{last}-1$ choices, total $(2^{last}-1)^{cur}$
- Edges between vertices at the same level are optional. Total $\binom{cur}{2}$
- The graph is numbered, where the indices of the previous $i-cur$ vertices have already been determined, and the index of the vertex $n$ has also been determined. So choose $cur$ vertices among $n-(i-cur)-1$ vertices: $\binom{n-i+cur-1}{cur}$. The transition of the last level is an exception, because the vertex $n$ is also included, so the calculation formula of the last level is $\binom{n-i+cur}{cur}$
Multiply these counts:
$$dp[i][cur]=\sum(dp[i-cur][last]\times (2^{last}-1)^{cur}\times \binom{cur}{2}\times \binom{n-i+cur-1}{cur})$$
$$dp[n][cur]=\sum(dp[i-cur][last]\times (2^{last}-1)^{cur}\times \binom{cur}{2}\times \binom{n-i+cur}{cur})$$
Answer is $dp[n][1]$
// compile: g++ -o data data.cpp -O3 -std=gnu++20 -Wall -Wextra -Wshadow -D_GLIBCXX_ASSERTIONS -ggdb3 -fmax-errors=2 -DLOCAL
// run: ./data < data.in
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#ifdef LOCAL
#include <debug/codeforces.h>
#define debug(x...) {_variables(#x);_print(x);}
#else
#define debug(x...)
#endif
template<typename...Args> void print_(Args...args){((cout<<args<<" "),...)<<endl;}
#define rep(i,a,b) for(int i=(a);i<(int)(b);++i)
#define sz(v) ((int)(v).size())
#define print(...) print_(__VA_ARGS__);
#define INTMAX (int)(9223372036854775807)
#define INTINF (int)(1152921504606846976)
#define int long long
#define MAXN 1010
namespace atcoder{namespace internal{template<class T>using is_integral=typename std::is_integral<T>;template<class T>using is_signed_int=typename std::conditional<is_integral<T>::value&&std::is_signed<T>::value,std::true_type,std::false_type>::type;template<class T>using is_unsigned_int=typename std::conditional<is_integral<T>::value&&std::is_unsigned<T>::value,std::true_type,std::false_type>::type;template<class T>using to_unsigned=typename std::conditional<is_signed_int<T>::value,std::make_unsigned<T>,std::common_type<T>>::type;template<class T>using is_signed_int_t=std::enable_if_t<is_signed_int<T>::value>;template<class T>using is_unsigned_int_t=std::enable_if_t<is_unsigned_int<T>::value>;template <class T>using to_unsigned_t=typename to_unsigned<T>::type;constexpr int safe_mod(int x,int m){x%=m;if(x<0)x+=m;return x;}struct barrett{unsigned int _m;unsigned int im;explicit barrett(unsigned int m):_m(m),im((unsigned int)(-1)/m+1){}unsigned int umod()const{return _m;}unsigned int mul(unsigned int a,unsigned int b)const{unsigned int z=a;z*=b;unsigned int x=(unsigned int)(((unsigned __int128)(z)*im)>>64);unsigned int y=x*_m;return(unsigned int)(z-y+(z<y?_m:0));}};constexpr std::pair<int,int> inv_gcd(int a,int b){a=safe_mod(a,b);if(a==0){return{b,0};}int s=b,t=a;int m0=0,m1=1;while(t){int u=s/t;s-=t*u;m0-=m1*u;auto tmp=s;s=t;t=tmp;tmp=m0;m0=m1;m1=tmp;}if(m0<0)m0+=b/s;return{s,m0};}constexpr int pow_mod_constexpr(int x,int n,int m){if(m==1)return 0;unsigned int _m=(unsigned int)(m);unsigned int r=1;unsigned int y=safe_mod(x,m);while(n){if(n&1)r=(r*y)% _m;y=(y*y)% _m;n>>=1;}return r;}constexpr bool is_prime_constexpr(int n){if(n<=1)return false;if(n==2||n==7||n==61)return true;if(n%2==0){return false;}int d=n-1;while(d%2==0)d/=2;constexpr int bases[3]={2,7,61};for(int a:bases){int t=d;int y=pow_mod_constexpr(a,t,n);while(t!=n-1&&y!=1&&y!=n-1){y=y*y%n;t<<=1;}if(y!=n-1&&t%2==0){return false;}}return true;}template <int n>constexpr bool is_prime=is_prime_constexpr(n);struct modint_base{};struct static_modint_base:modint_base{};template <class T>using is_modint=std::is_base_of<modint_base,T>;template <class T>using is_modint_t=std::enable_if_t<is_modint<T>::value>;}template <int m,std::enable_if_t<(1<=m)>* =nullptr>struct static_modint:internal::static_modint_base{using mint=static_modint;public:static constexpr int mod(){return m;}static mint raw(int v){mint x;x._v=v;return x;}static_modint():_v(0){}template<class T,internal::is_signed_int_t<T>* =nullptr>static_modint(T v){int x=(int)(v %(int)(umod()));if(x<0)x+=umod();_v=(unsigned int)(x);}template <class T,internal::is_unsigned_int_t<T>* =nullptr>static_modint(T v){_v=(unsigned int)(v%umod());}unsigned int val()const{return _v;}mint&operator++(){_v++;if(_v==umod())_v=0;return *this;}mint&operator--(){if(_v==0)_v=umod();_v--;return *this;}mint operator++(int32_t){mint result=*this;++*this;return result;}mint operator--(int32_t){mint result=*this;--*this;return result;}mint&operator+=(const mint&rhs){_v+=rhs._v;if(_v>=umod())_v-=umod();return *this;}mint&operator-=(const mint&rhs){_v-=rhs._v;if(_v>=umod())_v+=umod();return *this;}mint&operator*=(const mint&rhs){unsigned int z=_v;z*=rhs._v;_v=(unsigned int)(z%umod());return *this;}mint&operator/=(const mint&rhs){return *this=*this*rhs.inv();}
mint operator+()const{return *this;}mint operator-()const{return mint()-*this;}mint pow(int n)const{assert(0<=n);mint x=*this,r=1;while(n){if(n&1)r*=x;x*=x;n>>=1;}return r;}mint inv()const{if(prime){assert(_v);return pow(umod()-2);}else{auto eg=internal::inv_gcd(_v,m);assert(eg.first==1);return eg.second;}}friend mint operator+(const mint&lhs,const mint&rhs){return mint(lhs)+=rhs;}friend mint operator-(const mint&lhs,const mint&rhs){return mint(lhs)-=rhs;}friend mint operator*(const mint&lhs,const mint&rhs){return mint(lhs)*=rhs;}friend mint operator/(const mint&lhs,const mint&rhs){return mint(lhs)/=rhs;}friend bool operator==(const mint&lhs,const mint&rhs){return lhs._v==rhs._v;}friend bool operator!=(const mint&lhs,const mint&rhs){return lhs._v!=rhs._v;}private:unsigned int _v;static constexpr unsigned int umod(){return m;}static constexpr bool prime=internal::is_prime<m>;};template<int id>struct dynamic_modint:internal::modint_base{using mint=dynamic_modint;public:static int mod(){ return(int)(bt.umod()); }static void set_mod(int m){assert(1<=m);bt=internal::barrett(m);}static mint raw(int v){mint x;x._v=v;return x;}dynamic_modint():_v(0){}template<class T,internal::is_signed_int_t<T>* =nullptr>dynamic_modint(T v){int x=(int)(v %(int)(mod()));if(x<0)x+=mod();_v=(unsigned int)(x);}template<class T,internal::is_unsigned_int_t<T>* =nullptr>dynamic_modint(T v){_v=(unsigned int)(v%mod());}unsigned int val()const{return _v;}mint&operator++(){_v++;if(_v==umod())_v=0;return *this;}mint&operator--(){if(_v==0)_v=umod();_v--;return *this;}mint operator++(int32_t){mint result=*this;++*this;return result;}mint operator--(int32_t){mint result=*this;--*this;return result;}mint&operator+=(const mint&rhs){_v+=rhs._v;if(_v>=umod()){_v-=umod();}return *this;}mint&operator-=(const mint&rhs){_v+=mod()-rhs._v;if(_v>=umod())_v-=umod();return *this;}mint&operator*=(const mint&rhs){_v=bt.mul(_v,rhs._v);return *this;}mint&operator/=(const mint&rhs){return *this=*this*rhs.inv();}mint operator+()const{return *this;}mint operator-()const{return mint()- *this;}mint pow(int n)const{assert(0<=n);mint x=*this,r=1;while(n){if(n&1)r*=x;x*=x;n>>=1;}return r;}mint inv()const{auto eg=internal::inv_gcd(_v,mod());assert(eg.first==1);return eg.second;}friend mint operator+(const mint&lhs,const mint&rhs){return mint(lhs)+=rhs;}friend mint operator-(const mint&lhs,const mint&rhs){return mint(lhs)-=rhs;}friend mint operator*(const mint&lhs,const mint&rhs){return mint(lhs)*=rhs;}friend mint operator/(const mint&lhs,const mint&rhs){return mint(lhs)/=rhs;}friend bool operator==(const mint&lhs,const mint&rhs){return lhs._v==rhs._v;}friend bool operator!=(const mint&lhs,const mint&rhs){return lhs._v!=rhs._v;}private:unsigned int _v;static internal::barrett bt;static unsigned int umod(){ return bt.umod(); }};template<int id>internal::barrett dynamic_modint<id>::bt(998244353);using modint998244353=static_modint<998244353>;using modint1000000007=static_modint<1000000007>;using modint=dynamic_modint<-1>;namespace internal{template<class T>using is_static_modint=std::is_base_of<internal::static_modint_base,T>;template<class T>using is_static_modint_t=std::enable_if_t<is_static_modint<T>::value>;template<class> struct is_dynamic_modint:public std::false_type{};template<int id>struct is_dynamic_modint<dynamic_modint<id>>:public std::true_type{};template<class T>using is_dynamic_modint_t=std::enable_if_t<is_dynamic_modint<T>::value>;}}
using mint = atcoder::modint;
mint C[MAXN][MAXN];
mint dp[MAXN][MAXN];
mint pow2[MAXN*MAXN];
mint powpow[MAXN][MAXN];
int32_t main() {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int n, M; cin >> n >> M;
mint::set_mod(M);
rep(i, 0, n+1) {
C[i][0] = 1;
rep(j, 1, i+1) C[i][j] = C[i-1][j-1] + C[i-1][j];
}
pow2[0] = 1; rep(i, 1, n*n+1) pow2[i] = pow2[i-1] * 2;
rep(i, 1, n+1) rep(j, 1, n+1) powpow[i][j] = mint(pow2[i] - 1).pow(j);
dp[1][1] = 1;
rep(i, 2, n+1) {
rep(j, 1, i+1) {
rep(k, 1, i-j+1) {
dp[i][j] = (dp[i][j] + dp[i-j][k] * powpow[k][j] * pow2[C[j][2].val()] * ((i==n) ? C[n-(i-j)][j] : C[n-(i-j)-1][j]));
}
}
}
cout << dp[n][1].val() << endl;
return 0;
}The size of the data for this question is very suspicious($n=500$), $O(n^3)$ algorithm seems to be difficult to pass. When encountering counting problems like this, try to layer the graph, bfs tree is a good entry point. Verify the correctness of the state transition function through some small data.