Codeforces #445 Div1 C. Maximum Element

これは割とすんなり解けた。
http://codeforces.com/contest/889/problem/C

問題

1～NのPermutationである数列Aがあったとする。
定数Kが与えられたとき、以下のアルゴリズムで正しい最大値Nを返さないAが何通りあるか求めよ。

int fast_max(int n, int a[]) { 
    int ans = 0;
    int offset = 0;
    for (int i = 0; i < n; ++i)
        if (ans < a[i]) {
            ans = a[i];
            offset = 0;
        } else {
            offset = offset + 1;
            if (offset == k)
                return ans;
        }
    return ans;
}

解法

正しく返す組み合わせ数を求め、N!から引けばよい。
よって以下正しく最大値を返す組み合わせ数を求めよう。

f(P) := 1～Pの順列Aのうち、最大値が最後の要素に来て、かつ上記アルゴリズムでそれを正しく返すような組み合わせ
とする。
元のAにおいてNがP要素目に来ているときにそれを正しく返すのは、先頭P要素について座標圧縮するとf(P)に含まれるような並び順であり、かつNがP要素目に来ている場合である。
またP要素目以降の並びはどうでもよいので、求めるのはである。

あとはf(P)を線形時間で求めることを考えよう。
先頭(P-1)要素中の最大値がA[Q]のとき、問題の条件よりP-Q≦Kでなければならない。
f(P)を満たす数列では、A[P]=PかつA[Q]=A-1である。
よってf(Q)より
これより、の累積和を取っておけばf(P)を順次線形時間で求めることができる。

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

ll combi(ll N_, ll C_) {
	if (fact[0]==0) {
		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;
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}
ll F[1010100];
ll FS[1010100];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	combi(1,1);
	cin>>N>>K;
	
	ll ret=0;
	for(i=1;i<=N;i++) {
		if(i<=K) {
			F[i]=fact[i-1];
		}
		else {
			(F[i]=(FS[i]-FS[i-K]+mo)*fact[i-2])%=mo;
		}
		(FS[i+1]=FS[i]+F[i]*factr[i-1])%=mo;
		(ret+=F[i]*combi(N-1,i-1)%mo*fact[N-i])%=mo;
	}
	
	cout<<(fact[N]+mo-ret)%mo<<endl;
}

まとめ

実際こんな最大値の求め方するかな…。