ミスが多すぎた。
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番目以降にあればいいのでf(i+1,y)=i∑x=yf(i,x)
- (i+1)が後ろに来る場合
- (i+1)をy番目に挿入する場合、元々iがy番目より手前にあればいいのでf(i+1,y)=y−1∑x=1f(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が上限と勘違いしてびっくりした。