yukicoder : No.829 成長関数インフレ中

これ系苦手。
https://yukicoder.me/problems/no/829

問題

整数列Aに対し、成長数g(A)をmax(A[0...(i-1)])＜A[i]であるようなiの数とする。

ここでN要素の整数列Sと定数Bが与えられる。
Sの並べ替えN!通りに対し、g(S)*B^g(S)の総和を求めよ。

解法

Sの要素を小さい順に挿入することを考える。
dp(i,j) := i番目まで挿入した状態で成長数がjであるような組み合わせ
dp(i,j)からdp(i+1,j)またはdp(i+1,j+1)に寄与するので、O(N^2)掛ければ解けるが、これでは間に合わない。

ただ、個々のdp(N,j)を愚直に求める必要はない。
例えば適当な係数P(i),Q(i)に対し、以下のような感じで状態が遷移するとする。

• dp(i+1,j+1) += P(i)×dp(i,j)
• dp(i+1,j) += Q(i)×dp(i,j)

関数とするととなる。
となり、微分するとが解となる。
は1次式を掛け合わせたものなので、合成関数の微分を考えるとよい。

int N,B;
ll mo=1000000007;
vector<int> V;

ll P[202020],Q[202020];
ll L[202020],R[202020];
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>>B;
	map<int,int> M;
	FOR(i,N) {
		cin>>x;
		M[x]++;
	}

	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;
	
	FORR(v,M) {
		V.push_back(v.second);
	}
	N=V.size();
	int S=0;
	R[N+1]=1;
	for(i=N-1;i>=0;i--) {
		S+=V[i];
		P[i]=comb(S-1,V[i]-1)*fact[V[i]]%mo;
		Q[i]=comb(S-1,V[i])*fact[V[i]]%mo;
		R[i+1]=R[i+2]*(P[i]*B%mo+Q[i])%mo;
	}
	ll ret=0;
	L[0]=1;
	FOR(i,N) {
		L[i+1]=L[i]*(P[i]*B%mo+Q[i])%mo;
		(ret+=L[i]*P[i]%mo*R[i+2])%=mo;
	}
	
	cout<<B*ret%mo<<endl;
	
	
}

まとめ

母関数の微分とかの問題は苦手意識が強い。