想定解より単純な解法。
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; }
まとめ
包除原理よりこっちのほうが楽な気はする。