これは割とすんなり。
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<<" "; } }
まとめ
順調で良かったね。