AtCoder ABC #281 : G - Farthest City

これはすんなり。
https://atcoder.jp/contests/abc281/tasks/abc281_g

問題

正整数Nが与えられる。
1～Nのラベルがついた連結無向グラフのうち、以下の条件を満たすものは何通りか。

• u=2～(N-1)に対し、頂点1-頂点uの最短距離は頂点1-頂点Nの距離より短い

解法

頂点1からの距離がDの点は、距離(D-2)以下の点とは隣接せず、距離(D-1)の点と1個以上隣接する。

f(d,n,m) := 距離d以下の点がn個あり、距離dの点がm個であるような組み合わせ
とする。
距離d+1の点をx個加えるとき、x個の各点は距離dの点と1個以上隣接する必要があり、またx個の点同士は隣接してもしなくてもよい。また、頂点1とN以外からx個選ぶ必要があるので、
f(d+1,n+x,x) += f(d,n,m) * (2^m-1)^x * 2^(x(x+1)/2) * Binom(N-2,x)
のように遷移する。
f(d,N-1,m)を求めたら、最後N番の頂点をm個のどこかにつなげることを考え、f(d,N-1,m) * (2^m-1)の総和を取ればよい。

int N;
ll mo;

ll dp[505][505];
ll p2[1202020];
ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

ll comb(int P_,int Q_) {
	static const int N_=1020;
	static ll C_[N_][N_];
	
	if(C_[0][0]==0) {
		int i,j;
		FOR(i,N_) C_[i][0]=C_[i][i]=1;
		for(i=1;i<N_;i++) for(j=1;j<i;j++) C_[i][j]=(C_[i-1][j-1]+C_[i-1][j])%mo;
	}
	if(P_<0 || P_>N_ || Q_<0 || Q_>P_) return 0;
	return C_[P_][Q_];
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>mo;
	dp[1][1]=1;
	p2[0]=1;
	FOR(i,N*N) p2[i+1]=p2[i]*2%mo;
	
	for(i=1;i<=N-2;i++) {
		for(j=1;j<=N;j++) if(dp[i][j]) {
			ll p=p2[j]-1;
			ll kv=dp[i][j];
			for(k=1;i+k<N;k++) {
				kv=(kv*p)%mo;
				(dp[i+k][k]+=kv*comb(N-1-i,k)%mo*p2[k*(k-1)/2])%=mo;
			}
		}
	}
	ll ret=0;
	for(j=1;j<=N;j++) ret+=dp[N-1][j]*(p2[j]-1)%mo;
	cout<<ret%mo<<endl;
	
}

まとめ

過去どこかで解いていそうな気もする。