Codeforces ECR #125 : E. Star MST

問題文は短め。
https://codeforces.com/contest/1657/problem/E

問題

整数N,Kが与えられる。
N頂点の無向完全グラフを考える。
各辺の重さは、1～Kの整数値を取る。

もしこのグラフのMSTを成す辺の重さの総和が、頂点1からつながる辺の重さの総和に一致するとき、グラフは美しいと呼ぶ。
美しいグラフは何通りか。

解法

点vと点1の距離がdの場合、点1との距離がd以下の点との距離はd以上でなければならない。
これを踏まえて、
dp(n,m) := 点1との距離がm以下の辺がn個であるような(n+1)頂点間の距離の組み合わせ
を求めて行けばよい。これはn,mに対し、点1との辺の長さがm+1である点を何個追加するかを総当たりすればよい。

int N,K;
const ll mo=998244353;

ll from[255],to[255];

const int NUM_=400001;
static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];

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;
	
	inv[1]=fact[0]=factr[0]=1;
	for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
	for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	
	cin>>N>>K;
	from[0]=fact[N-1];
	for(i=1;i<=K;i++) {
		ZERO(to);
		FOR(j,N+1) {
			for(x=0;j+x<=N-1;x++) {
				y=j*x+x*(x-1)/2;
				(to[j+x]+=from[j]*factr[x]%mo*modpow(K+1-i,y))%=mo;
			}
		}
		
		
		swap(from,to);
	}
	cout<<from[N-1]<<endl;
}

まとめ

DよりEの方が簡単でない？