kmjp's blog

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

yukicoder : No.1886 Sum of Slide Max

yukicoder

これ★3だけど、次の★3.5の方がだいぶ楽だったなぁ。
https://yukicoder.me/problems/no/1886

問題

1～NのPermutation Pと、整数Kに対しf_K(P)を次のように定義する。
\displaystyle f_K(P) = \sum_{i = 1}^{N - K + 1} \max \{P_i, P_{i+1}, \ldots, P_{i + K - 1} \}

Nが与えられたとき、N!通りあるすべてにPに対し、K=1～Nの時それぞれのf_K(P)の総和を求めよ。

解法

Kが定まったとき、 \displaystyle \max \{P_i, P_{i+1}, \ldots, P_{i + K - 1} \}がどうなるかを考える。

  • このK個にNが含まれていればN
  • このK個にNが含まれておらず、N-1が含まれていれば(N-1)
  • このK個に(N-1)～Nが含まれておらず、N-2が含まれていれば(N-2)
  • …

言い換えると、

  • 「K個に**が含まれていない」は言い換えると「残り(N-K)個に**が含まれている」なので、

この組み合わせを考えると期待値は[ \displaystyle \frac{\sum_i \left( {}_{N-i-1} C_{K-1} \times (N-i) \right)}{{}_N C_K}となる。
このsumの部分は式変形すると \displaystyle K \times {}_{N-i+1} C_{i+1}となる。

int N;
const ll mo=998244353;
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;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	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;
	for(i=1;i<=N;i++) {
		ll a=i*comb(N+1,i+1)%mo*(N+1-i)%mo;
		a=a*fact[i]%mo*fact[N-i]%mo;
		
		cout<<a<<endl;
	}
	
}

まとめ

実装は簡単なんだけど、立式と式変形に手間取った。