Deltix Round Spring 2021 : E. Crypto Lights

解は短い。
https://codeforces.com/contest/1523/problem/E

問題

整数N,Kが与えられる。
N個の電球が並んでおり、初期状態でいずれも消灯している。
ここで、ランダムな順で消灯中の電球を1つずつ点灯していく。

途中、どの連続するK電球にも1個以上点灯している電灯が現れたとき、以降の点灯を止めるとする。
点灯を止めるまでに点灯させる電球の期待値を求めよ。

解法

f(n) := n個電球を点灯させたとき、点灯させた電球の間隔がK以上である確率
とすると、解は1+f(1)+f(2)+...となる。
f(n)は、先に点灯した電球間にK個ずつ消灯した電球を配置させておくと、残った消灯電球をどこに挟むかで二項係数を使い容易に計算できる。

int T;
int N,K;
const ll mo=1000000007;
const int NUM_=400001;
static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];

ll comb(ll N_, ll C_) {
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}
ll hcomb(int P_,int Q_) { return (P_==0&&Q_==0)?1:comb(P_+Q_-1,Q_);}


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>>T;
	while(T--) {
		cin>>N>>K;
		
		ll ret=1;
		for(i=1;i<=N;i++) {
			int need=(i-1)*K+1;
			if(need>N) break;
			(ret+=hcomb(i+1,N-need)*fact[i]%mo*fact[N-i]%mo*factr[N])%=mo;
		}
		cout<<ret<<endl;
		
	}
}

まとめ

実際本番もDより短い時間で解いてるな。