Codeforces #178 Div2. C. Shaass and Lights

この回はDiv2 Onlyなので後で復習だけ。
D,Eは面白い問題だったな。まずはCから。
http://codeforces.com/contest/294/problem/C

問題

1～N番の電球が一列に並んでおり、うちいくつか点いている電球の番号が与えられる。
ここで残りの電球を点けていくが、その際隣に点いている電球がある場合のみ電球を点けられる。
全部電球が点くまでの、点け方の順序の組み合わせ数を答えよ。

解法

最初に点いている電球を除くと、いくつかの点いてない電球列があることがわかる。
求めるのは、（どの電球列を点けるかの並び）×（各電球列内の並び）である。

点いてない電球列について、その数を順にA[0]、A[1]、A[2]…、A[M-1]のM個の列があるとすると、

• 前者は単純に(A[0]+…+A[M-1])=L個の電球のうち、A[0]、A[1]…回ずつ電球列を選べばよいので単なる組み合わせ演算で
• 個々の電球列について、先頭と末尾の電球列だけは、点いている電球から1個ずつ点けていくしかないので電球列内の点ける順番は1通り。それ以外は、電球列の両端から1つずつつけていけるので、それぞれ通り。

両者を掛け算すればよい。
組み合わせ数の掛け算のためにパスカルの三角形を作るのでO(N^2)かな。

int N,M;
vector<int> P;

ll mo=1000000007;
ll addmod(ll& l,ll r){ return l=(((l+r)%mo)+mo)%mo;}

ll comb(int P_,int Q_) {
	static const int N_=1020;
	static ll C_[N_][N_];
	if(C_[0][0]==0) {
		int i,j;
		FOR(i,N_) C_[i][0]=C_[i][i]=1;
		for(i=1;i<N_;i++) for(j=1;j<i;j++) C_[i][j]=(C_[i-1][j-1]+C_[i-1][j])%mo;
	}
	return C_[P_][Q_];
}

void solve() {
	int f,r,i,j,k,l,x,y,cur,tar;
	
	N=GETi();
	M=GETi();
	FOR(i,M) P.push_back(GETi()-1);
	sort(P.begin(),P.end());
	
	ll res=1;
	res = (comb(N-M,P[0]) * comb(N-M-P[0],N-P[P.size()-1]-1)) % mo;
	M+=P[0]+(N-P[P.size()-1]-1);
	
	FOR(i,P.size()-1) {
		if(P[i+1]-P[i]>1) {
			res = (res * comb(N-M,P[i+1]-P[i]-1)) % mo;
			M+=P[i+1]-P[i]-1;
			FOR(j,P[i+1]-P[i]-2) res = (res*2)%mo;
		}
	}
	
	_P("%lld\n", res);
	return;
}

まとめ

シンプルな題材でよくこういう問題を作れるなぁ。