kmjp's blog

競技プログラミング参加記です

AtCoder ABC #389 (トヨタ自動車プログラミングコンテスト2025) : G - Odd Even Graph

これは割とすんなり。
https://atcoder.jp/contests/abc389/tasks/abc389_g

問題

整数N、素数Pが与えられる。
M=(N-1)~N*(N-1)/2のそれぞれに対し、以下に答えよ。

1~NのN点とM辺からなる無向グラフのうち、頂点1からの距離が奇数の点と偶数の点の数が一致するものは何通りか。Pで割った値を求めよ。

解法

頂点1から距離dの点が持てる辺は以下の通り。

  • 距離(d-1)の点と、1つ以上辺がなければならない。
  • 距離dの他の点とは、辺があってもなくてもよい。
  • 他の点とは、辺があってはならない。

これを踏まえで、距離0,1,2....と順に頂点数を定めることを考える。

dp(sum,pre,dif,e) := sumは定めた頂点数、preは頂点0から最遠となる頂点数、difは最遠となる頂点と偶奇が一致する点と一致しない点の差、eはこれまでの辺の数
とする。状態として距離を明に持たなくてよい点に注意。
求めたいのはdp(N,*,0,M)の和である。

あらかじめ以下の値を求めておく。
dp2(x,y,e) := 距離(d-1)の点がx、距離dの点がyとなるように、距離(d-1)の点と距離dまたは距離dの点同士の辺を張るとき、辺の数がeとなる組み合わせ
これはxを固定して、yを小さい順に埋めることができる。

dp(sum,pre,dif,e)の状態に対し、最遠点より距離が1多い点をv点・f辺追加する場合、
dp(sum+v,v,-(dif-v),e+f) += dp(sum,pre,dif,e) * dp2(pre,v,f) * C(N-sum,v)
として状態遷移するとよい。
dp2を埋める前処理がO(N^4)、dpを埋める処理がO(N^8)で終わる。

ll mo;
int N;

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_];
}

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 dp[32][32][32][900];
// 点の数・直前の点・偶奇の差・辺

ll dp2[32][32][900];
// a点とb点の間にe辺がある

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>mo;
	
	for(x=1;x<=N;x++) {
		dp2[x][0][0]=1;
		for(y=0;x+y<N;y++) {
			for(int e=0;e<=800;e++) if(dp2[x][y][e]) {
				for(i=1;i<=x;i++) for(j=0;j<=y;j++) {
					(dp2[x][y+1][e+i+j]+=dp2[x][y][e]*comb(x,i)%mo*comb(y,j))%=mo;
				}
			}
		}
	}
	
	dp[1][1][16][0]=1;
	
	for(int sum=1;sum<N;sum++) {
		for(int pre=1;pre<=sum;pre++) {
			for(int dif=0;dif<=30;dif++) {
				for(int e=0;e<=N*N;e++) if(dp[sum][pre][dif][e]) {
					for(int addv=1;sum+addv<=N;addv++) {
						for(int adde=addv;adde<=pre*addv*adde&&adde+e<=N*(N-1)/2;adde++) if(dif-addv>=0&&dif-addv<=30&&dp2[pre][addv][adde]) {
							(dp[sum+addv][addv][30-(dif-addv)][e+adde]+=dp[sum][pre][dif][e]*dp2[pre][addv][adde]%mo*comb(N-sum,addv))%=mo;
						}
					}
				}
			}
		}
	}
	
	for(i=N-1;i<=N*(N-1)/2;i++) {
		ll sum=0;
		FOR(j,N+1) sum+=dp[N][j][15][i];
		cout<<sum%mo<<" ";
	}
	
}

まとめ

順調で良かったね。