kmjp's blog

競技プログラミング参加記です

CSAcademy Round #40 : D. Restricted Permutations

ミスが多すぎた。
https://csacademy.com/contest/round-40/task/restricted-permutations/

問題

1~NのPermutationを成す数列を考える。
この時、iと(i+1)はどちらが手前に来るか、という情報が各iに対し与えられる。
条件を満たす数列は何通りあるか答えよ。

解法

幸いNは小さいのでO(N^2)で通る。
小さい順に並び順を確定させていくことを考える。
f(i,x) := 1~iまでを並べたとき、iがi個中初めからx番目にある場合の組み合わせ

次に(i+1)をiの手前に置くか後に置くかが与えられるので、それをもとに置き場所を考えよう。

  • (i+1)が手前に来る場合
    • (i+1)をy番目に挿入する場合、元々iがy番目以降にあればいいので \displaystyle f(i+1,y) = \sum_{x=y}^i f(i,x)
  • (i+1)が後ろに来る場合
    • (i+1)をy番目に挿入する場合、元々iがy番目より手前にあればいいので \displaystyle f(i+1,y) = \sum_{x=1}^{y-1} f(i,x)

yを増減させながら処理するとき、sumの値を使いまわせば全体でO(N^2)で済む。
あとはsum(f(N,*))を答えるだけ。

int N;
int A[2020];
ll from[2020];
ll to[2020];
ll mo=1000000007;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) cin>>A[i];
	
	from[0]=1;
	for(i=2;i<=N;i++) {
		ZERO(to);
		ll tot=0;
		if(A[i-2]==0) {
			for(j=i-1;j>=0;j--) {
				tot+=from[j];
				to[j]=tot%mo;
			}
		}
		else {
			FOR(j,i) {
				to[j]=tot%mo;
				tot+=from[j];
			}
		}
		swap(from,to);
	}
	
	cout<<accumulate(from,from+N+1,0LL)%mo<<endl;
	
}

まとめ

N=10^5が上限と勘違いしてびっくりした。