TopCoder SRM 656 Div1 Medium PermutationCounts、Div2 Hard PermutationCountsDiv2

良い問題だと思うが、自力でこの解法は求められない…。
http://community.topcoder.com/stat?c=problem_statement&pm=13550
http://community.topcoder.com/stat?c=problem_statement&pm=13739

問題

1～NのPermutationである数列Pを考える。
このPのうち、整数集合posに対してi∈posの場合P[i]＜P[i+1]、そうでない場合P[i]＞P[i+1]であるようなものの種類を求めよ。

解法

posの要素数をpとする。
posをソートすると、V=[pos[0]-0,pos[1]-pos[0],pos[2]-pos[1],...,N-pos[p-1]]という数列を考えると、Pはそれぞれ連続するV[i]個だけ連続降下列になっており、その境目では上昇するということになる。

上昇の条件を除くと、1～NをV[i]個ずつ分けてそれぞれ降順に並べればいいので解はとなる。
ここから、境界が上昇しないケース、すなわちV[i]+V[i+1]+...+V[j]が連続で降下するケースを引いていけば良い。

各V[i]とV[i+1]の間が上昇するか降下するかを総当たりすると2^p回手間がかかるので、うまく包除原理を使いp^2で処理していく。
このあたりは以下のForumを参考にすると良い。
TopCoder Forums

なお、上記Forumの記載は一部ミスがあるね。
N=9, pos=2,4,5の場合、V=[2,2,1,4]になるので解は

じゃないかな。
上の式を見ると、どう包除原理で解けるか想像つくね。
階乗の個数の偶奇で符号の正負が反転してる。

ll mo=1000000007;
ll dp[3000];

const int NUM_=1000001;
static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];

class PermutationCounts {
	public:
	int countPermutations(int N, vector <int> pos) {
		int i,j;
		
		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;
		
		pos.push_back(0);
		pos.push_back(N);
		sort(pos.begin(),pos.end());
		
		ZERO(dp);
		dp[0]=1;
		for(i=0;i<pos.size();i++) {
			FOR(j,i) {
				ll pat=dp[j]*factr[pos[i]-pos[j]]%mo;
				if((i-j)%2==0) dp[i] += mo-pat;
				else dp[i] += pat;
			}
			dp[i] %= mo;
		}
		
		return dp[pos.size()-1]*fact[N]%mo;
	}
}

まとめ

こんな包除原理の適用は自力では思いつかない…。