Codeforces #1015 : E. Blossom

こちらは余り苦労せず解いてるな。
https://codeforces.com/contest/2084/problem/E

問題

0～(N-1)のPermutation Aが与えられる。
ただしAの一部は不定である。

Aの不定の箇所に値を埋めたとき、各部分列のmex値の総和を求めよ。

解法

f(n) := Aのうちmex値がn以上であることが確実(=0～(n-1)が含まれる)部分列の数
とすると、求めるのはsum(f(n))となる。
nをだんだん大きくしていきながら、あり得る左端の上限と右端の下限を求めよう。
その際、取りえる部分列を、不定要素の数毎にカウントする。

数列内の不定要素の数がわかれば、0～(n-1)が含まれるような不定要素の埋め方がわかる。

int T,N;
int A[5050];
const ll mo=1000000007;

int F[5050][5050];
int C[5050];
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;
}

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;
	
	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;
		FOR(i,N) cin>>A[i];
		ZERO(C);
		FOR(x,N) {
			k=0;
			for(y=x;y<N;y++) {
				if(A[y]==-1) k++;
				F[x][y]=k;
				C[k]++;
			}
		}
		int L=N,R=-1;
		ll ret=0;
		int all=F[0][N-1];
		int need=0;
		FOR(i,N) {
			k=-1;
			FOR(j,N) if(A[j]==i) k=j;
			if(k==-1) {
				need++;
			}
			else {
				if(L==N) {
					FOR(x,N) for(y=x;y<N;y++) if(y<k||x>k) C[F[x][y]]--;
					L=R=k;
				}
				else {
					if(k<L) {
						for(x=k+1;x<=L;x++) for(y=R;y<N;y++) C[F[x][y]]--;
					}
					if(k>R) {
						for(y=R;y<k;y++) FOR(x,L+1) C[F[x][y]]--;
					}
					L=min(L,k);
					R=max(R,k);
				}
			}
			FOR(j,N+1) if(C[j]) (ret+=C[j]*comb(j,need)%mo*modpow(comb(all,need))%mo)%=mo;
		}
		(ret*=fact[all])%=mo;
		cout<<ret<<endl;
		
	}
}

まとめ

他で出てきても不思議じゃなさそうな問題。