ARC104 E - Random LIS 解説
ちょっとだけ面白い解き方をしたので解説として残しておく。
E - Random LIS
問題概要
長さの数列は、番目の要素がを満たす整数として一様分布で与えられる。最長増加部分列の長さの期待値を求めよ。
解法
LISはの大小関係で完全に決まるから、大小関係が一致しているような数列を数え上げられれば十分。
大小関係の型の取り方は、まず一致しているかどうかを無視して通りの順番で並べ、隣接する2つが一致しているか否かの通りを考えば良い。この際被ったもの(例えばは同じ関係である)は適当に無視すれば良い。
あとは大小関係の型が一致する数列を数え上げれば良い。このとき一致している項に関してはの最小を上限として選べるので、長さの数列が、番目の要素としての範囲を全て動くとき、単調増加列の数を数え上げるという問題に言い換えられた(ここまでがわからなかったら公式解説とか読んで)。
「初項が以上であるような長さの数列が、番目の要素としての範囲を全て動くとき、単調増加列の数」をと定義する。ただし与えられるは単調増加として良い。*1このとき求めるべきはとなる。ここでから初項を除いた数列を考えると
となることに注意する。ここで上昇階乗冪というものを導入する。
このとき、重要な性質として
が成立する(証明は簡単)。これを利用して実際にを求める。が次の上昇階乗冪多項式で表せることを帰納的に示す。
のとき、数列は空なので通りであるからとなり条件を満たす。
のとき、長さで成立しているとしてと書けたとする。このとき
となり、示された。
上昇階乗冪多項式で表せることを示したついでに、具体的な計算方法もわかったので、あとは計算するだけである。
最後に計算量を確認する。次上昇階乗冪多項式の積分操作は素朴にやって*2、代入操作は素朴にやるとかかるが、上昇階乗冪を下位の次数から順番に求めればで実行できる。よって再帰1回はで実行されているから、全体でで計算される。Ordered Bell numberをとすれば、全体の計算量はとなり、に注意して十分高速である。
実装例
#include<bits/stdc++.h> #include<atcoder/all> using namespace std; using namespace atcoder; using ll=long long; template<class T,class U> inline bool chmin(T&x,U y){if(x>y){x=y;return true;}return false;} template <class T> int LIS(vector<T>&a){ int n=a.size(); vector<T> l(n+1,numeric_limits<T>::max()); for(int i{};i<(n);++i){ *lower_bound(l.begin(),l.end(),a[i])=a[i]; } for(int i{1};i<=(n);++i){ if(l[i]==numeric_limits<T>::max()) return i; } } using mint=modint1000000007; mint substitution(const vector<mint>&f,mint x){ mint ans{},X{1}; int n=f.size(); for(int i{};i<(n);++i){ ans+=f[i]*X; X*=x; ++x; } return ans; } vector<mint> rec(vector<int>&a){ if(a.empty()) return {1}; int A=a.back(); a.pop_back(); auto D=rec(a); int n=D.size(); vector<mint> I(n+1); for(int i{1};i<=(n);++i){ I[i]=-D[i-1]/i; } I[0]=-substitution(I,A+1); return I; } void solve(){ unsigned n; cin>>n; vector<int> a(n); for(auto&i:a) cin>>i; vector<int> p(n); iota(p.begin(),p.end(),0); set<vector<vector<int>>> st; do{ for(unsigned j{};j<(1u<<(n-1));++j){ vector<vector<int>> v(1); unsigned b=j; for(auto&i:p){ v.back().push_back(i); if(b&1u) v.emplace_back(); b>>=1u; } for(auto&u:v) sort(u.begin(),u.end()); st.insert(v); } }while(next_permutation(p.begin(),p.end())); mint ans{}; for(auto&v:st){ int N=v.size(); vector<int> T(n),A(N,INT_MAX); for(int i{};i<(N);++i){ for(auto&j:v[i]){ T[j]=i; chmin(A[N-1-i],a[j]); } } for(int i{1};i<(N);++i){ chmin(A[i],A[i-1]); } mint P=substitution(rec(A),1); int L=LIS(T); ans+=P*L; } for(int i{};i<(n);++i){ ans/=a[i]; } cout<<ans.val()<<'\n'; } int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); solve(); }
まとめ
コンテスト中にΣ6個くっついた変数11個のやつそのまま手元で公式求めて打ち込もうとして、WolframがΣ5つで音をあげやがったやつを改良していい感じに解けた。解説ででやってるところをでやってるのでいい感じかも。