オンサイトにしてはマイルドな難易度？
https://beta.atcoder.jp/contests/soundhound2018-summer-final-open/tasks/soundhound2018_summer_final_c
問題
正整数N,Dに対し、以下を満たす無向グラフの組み合わせを求めよ。
- N頂点の無向グラフで、自己辺・多重辺をもたない。
- 各頂点は1～Nの番号を持つ。
- 1番から2番の頂点の最短距離はDである。
解法
以下の値を考える。
f(d, left, pre) := 1番の頂点から距離d以下の頂点までの配置を決めたとき、残り未配置の頂点がleft個であり、距離dの頂点がpre個である。
1番と2番の頂点を除いた(N-2)個の頂点の並び順を決めるので、f(0,N-2,1)から順に上記値を埋めていこう。
距離dの頂点のうち1個以上とつながる頂点は距離d+1となるので、距離d+1の点がx個ある場合を考えて以下の和を取っていく。
f(d+1, left-x, x) += f(d, left, pre) * comb(left, x) * (2^comb(x,2)) * *1^left)*(2^comb(left,2))が加算される。
(2^pre-1)は、2番の頂点は距離(D-1)にあるpre個のいずれかの頂点と接続する必要があることを意味する。
*2^left)は、残りleft個の頂点は距離(D-1)にあるpre個および2番の頂点計(pre+1)個の頂点の間の辺の有無の組み合わせを意味する。
最後の(2^comb(left,2))は、left個の点同士の間は辺があってもなくてもよいことを示す。
int N,D; ll mo=1000000007; ll dp[31][31][31]; const int CN=41; ll C[CN][CN]; ll p2[1010]; 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; } void solve() { int i,j,k,l,r,x,y; string s; FOR(i,CN) for(j=0;j<=i;j++) C[i][j]=(j==0||j==i)?1:(C[i-1][j-1]+C[i-1][j])%mo; p2[0]=1; FOR(i,1000) p2[i+1]=p2[i]*2%mo; cin>>N>>D; dp[1][N-2][1]=1; for(i=2;i<=D;i++) { for(int left=1;left<=N-2;left++) { for(int pre=1;pre<=N-2;pre++) if(dp[i-1][left][pre]) { for(x=1;x<=left;x++) (dp[i][left-x][x]+=dp[i-1][left][pre]*C[left][x]%mo*p2[x*(x-1)/2]%mo*modpow(p2[pre]+mo-1,x))%=mo; } } } ll ret=0; for(int left=0;left<=N-1;left++) { for(x=1;x<=N-1;x++) if(dp[D][left][x]) { (ret+=dp[D][left][x]*(p2[x]+mo-1)%mo*modpow(p2[x+1],left)%mo*p2[left*(left-1)/2])%=mo; } } cout<<ret<<endl; }
まとめ
最初木・森縛りがあると勘違いして、「これO(N^3)で行けるのになんでNの上限が小さいんだ？」と思ってしまった。
