TopCoder SRM 772 : Div1 Easy SmoothPermutations

不参加でした。
https://community.topcoder.com/stat?c=problem_statement&pm=15783

問題

1～NのPermutationのうち、先頭K個の上限がX以下の物は何通りか。
mod Mで求めよ。

解法

K個並べるので最低でも上限はK必要であり、K＞Xなら0個。
以後K≧Xとして考える。
Xより大きな(N-X)要素は後ろ(N-K)通りしか置けないので、modを除くと解は。
あいにくこの問題ではMは素数とは限らないので、除算はできればしたくない。
そこで、1～Nのうち任意の区間の積を求めるSegTreeを作っておけば、上記式はそれぞれO(N logN)で求められる。

ll A[606060];

ll mo=1000000007;
ll comb(ll N_, ll C_) {
	const int NUM_=400001;
	static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
	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;
}

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=1;
	V comp(V l,V r){ return l*r%mo;};
	
	SegTree_1(){val=vector<V>(NV*2,def);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=v%mo; //上書きかチェック
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};
SegTree_1<ll,1<<20> st;

class SmoothPermutations {
	public:
	long long countPermutations(int T, int M, int MX, int seed, vector <int> N, vector <int> K, vector <int> X) {
		
		mo=M;
		int i;
		FOR(i,202020) st.update(i,i);
		A[0]=seed;
		for(i=1;i<3*T;i++) A[i]=(A[i-1]*1103515245 + 12345)%2147483648;
		int l=N.size();
		for(i=l;i<T;i++) {
			N.push_back(A[i]%MX+1);
			K.push_back(A[T+i]%N[i]+1);
			X.push_back(A[2*T+i]%N[i]+1);
		}
		
		ll ret=0;
		FOR(i,T) {
			if(X[i]<K[i]) continue;
			
			ll a=st.getval(X[i]-K[i]+1,X[i]+1);
			ll b=st.getval(1,N[i]-K[i]+1);
			ret+=a*b%mo;
		}
		return ret;
	}
}

まとめ

疑似乱数による入力の生成と、任意modのCombination計算のための労力でなんかくたびれる問題。