yukicoder : No.1001 注文の多い順列

想定解より単純な解法。
https://yukicoder.me/problems/no/1001

問題

1～NのPermutation Pを作る。
各要素P[i]に対して、以下のいずれかの条件が与えられる。

• 定数X[i]に対し、P[i]≦X[i]
• 定数X[i]に対し、P[i]≧X[i]

条件を満たす数列は何通りか。

解法

条件を並べ替えても解は同じなので、前者と後者それぞれX[i]順にソートしよう。
前者のX[i]を集めた数列をA,後者のX[i]を集めた数列をBとする。

f(x,y) := 1～(x+y)までの値の配置を決めたとき、前者のタイプの条件の要素をx個、後者のタイプの条件の要素をy個埋めた状態で、条件に違反していない組み合わせ数
とする。次に(x+y+1)をどこに置くかを考える。

• 後者のタイプの条件の要素への埋め方ははわかりやすい。後者のタイプのうち、格納可能な位置はBのうち(x+y+1)以下の値となっている箇所である。そのような箇所がs個あるとして、うちy個はすでに埋まっているので、f(x,y+1) += f(x,y)*(s-y)となる。
• 前者だが逆に考えよう。(x+y+1)～Nをこれから埋める際に、うち|A|-x箇所だけ前者のタイプを埋めないといけない。今(x+y+1)を前者のタイプの要素に埋めるなら、その候補はAのうち(x+y+1)以上となっている箇所である。そのような箇所がt個あるとして、うち(|A|-(x+1))は今後埋めるために残しておかないといけないので、f(x,y+1) += f(x,y)*(t-(|A|-(x+1))となる。

int N;
vector<int> V[2];

ll dp[3030][3030];
const ll mo=1000000007;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>x>>y;
		V[x].push_back(y-1);
	}
	
	dp[0][0]=1;
	FOR(i,N) {
		int cand0=0;
		int cand1=0;
		FORR(v,V[0]) cand0+=v>=i;
		FORR(v,V[1]) cand1+=i>=v;
		FOR(x,V[0].size()+1) {
			y=i-x;
			if(y<0||y>V[1].size()) continue;
			if(x<V[0].size()) (dp[x+1][y]+=dp[x][y]*(cand0-(V[0].size()-x-1)))%=mo;
			if(y<V[1].size()) (dp[x][y+1]+=dp[x][y]*(cand1-y))%=mo;
		}
	}
	ll ret=0;
	FOR(i,N+1) ret+=dp[i][N-i];
	cout<<ret%mo<<endl;
}

まとめ

包除原理よりこっちのほうが楽な気はする。