yukicoder : No.2544 Many RMQ Problems

この言い換えはうまくできた。
https://yukicoder.me/problems/no/2544

問題

整数N,Qが与えられる。
1～Nの順列Pに対し、以下のクエリがQ個与えられることを考える。
i番のクエリでは区間[L[i],R[i]]が与えられるので、P[L[i]]....P[R[i]]の最小値をクエリの解とする。

P及びクエリ全パターンにおいて、クエリの解の総和を求めよ。

解法

各クエリは独立に考えればよい。
クエリの組み合わせは(N*(N+1)/2)通りあるので、1つのクエリに対する解がXなら、Q*X*(N*(N+1)/2)^(Q-1)を答えればよい。
あとはXを考える。

クエリが固定されていて、その長さがAの時の解をf(A)とすると、クエリの先頭位置の組み合わせが(N-A+1)であることを考えるとf(A)*(N-A+1)が解となる。
1～NのうちA個を選び、その最小値の総和を考えると、これはC(N+1,A+1)で計算できる。
区間内のA個及び区間外の(N-A)個の並び方は任意であることを考えると、f(A)=C(N+1,A+1)*A!*(N-A)!である。

int N,Q;
const ll mo=998244353;

const int NUM_=2400001;
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 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>>Q;
	ll ret=0;
	for(int len=1;len<=N;len++) {
		(ret+=(N-len+1)*comb(N+1,len+1)%mo*fact[len]%mo*fact[N-len]%mo)%=mo;
	}
	ll pat=1LL*N*(N+1)/2%mo;
	ret=ret*Q%mo*modpow(pat,Q-1)%mo;
	cout<<ret<<endl;
	
}

まとめ

ここら辺の二項定数の計算をうまく組めると気持ちよいよね。