これどっかで出てそう。
https://yukicoder.me/problems/no/992
問題
整数列A[i]が与えられる。
この部分列のうち、元の整数列のLISとなるものは何通りか。
部分列の値が同じでも、抽出した位置が違う数列は別物とする。
解法
まず、各要素がLISを構築する際何要素目になるかを求めよう。
i番目の要素がLISに入るとするとf(i)番目に入るものとする。
どうLISを構築しても、各要素が来る位置が変わることはない。
次にLISの構築の仕方を考えるわけだが、仮にA[i]をLISに加える場合、その直前の要素jは、
- j<i
- A[j]<A[i]
- f(j)+1=f(i)
でなければならない。
そのようなjに対し、A[0...(i-1)]の部分列のうちA[j]を末尾とするような組み合わせの総和がA[i]を末尾とするケースとなる。
これを求めるには、添え字順を変えたBITで累積和を求めればよい。
以下のように並べかえる。
- f(x) < f(y)ならxが手前
- f(x)==f(y)ならxとyの大きいほうの添え字が手前
こうすると上記総和を求める処理が数列中の区間和となるので、BITを利用できるようになる。
int N; int A[202020],B[202020]; int ID[202020],IDnum[202020],IDs[202020]; int num[202020]; ll dp[202020]; int V[202020]; ll mo=1000000007; template<class V, int ME> class BIT { public: V bit[1<<ME]; V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s%mo;} void add(int e,V v) { e++; while(e<=1<<ME) (bit[e-1]+=v)%=mo,e+=e&-e;} }; BIT<ll,20> bt; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; V[0]=-1<<30; FOR(i,N) V[i+1]=1<<30; int ma=0; FOR(i,N) { cin>>A[i]; x=lower_bound(V,V+N+1,A[i])-V; ID[i]=x; ma=max(ma,x); IDnum[i]=++num[x]; V[x]=A[i]; } IDs[1]=1; for(i=2;i<=ma;i++) IDs[i]=IDs[i-1]+num[i-1]; B[0]=-1<<30; FOR(i,N) B[IDs[ID[i]]+num[ID[i]]-IDnum[i]]=A[i]; ll ret=0; bt.add(0,1); FOR(i,N) { x=lower_bound(B+IDs[ID[i]-1],B+IDs[ID[i]],A[i])-B; x--; dp[i]=(bt(x)-bt(IDs[ID[i]-1]-1)+mo)%mo; if(ID[i]==ma) ret+=dp[i]; bt.add(IDs[ID[i]]+num[ID[i]]-IDnum[i],dp[i]); } cout<<ret%mo<<endl; }
まとめ
方針はすぐ思いついたけど割と手間取った。