HHKB プログラミングコンテスト 2020 : F - Random Max

想定解ではない気がする。
https://atcoder.jp/contests/hhkb2020/tasks/hhkb2020_f

問題

N個の区間[L[i],R[i]]が与えられる。
N要素の数列Xの各要素X[i]は、[L[i],R[i]]の一様分布から選択されるものとする。
全要素の最大値の期待値をEとしたとき、E*(N+1)!*prod(R[i]-L[i])を答えよ。

解法

以下O(N^3)解法なので非想定解かも。
まず区間を座標圧縮しておく。

以下を求めよう。愚直にDPすると、一部累積和を使いつつO(N^3)となる。
dp(i,x,y) := Xのprefix i番目までを見たとき、最大値はx番目の区間にあり、同着でy個存在するような確率

dp(N,x,y)が求められたら、次にEを考える。
座標圧縮したx番目の区間が[S,T]だとすると、最大値の期待値は[S,T]をy:1に内分した点になる。
なのでdp(N,x,y)*(S*y+T)/(y+1)の総和を取ろう。

int N;
int L[1010],R[1010];
const ll mo=1000000007;
vector<ll> V;

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

ll dp[2020][1010];
ll sum[2020];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	V.push_back(0);
	FOR(i,N) {
		cin>>L[i]>>R[i];
		V.push_back(L[i]);
		V.push_back(R[i]);
	}
	
	sort(ALL(V));
	V.erase(unique(ALL(V)),V.end());
	dp[0][1]=1;
	sum[0]=1;
	
	FOR(i,N) {
		L[i]=lower_bound(ALL(V),L[i])-V.begin();
		R[i]=lower_bound(ALL(V),R[i])-V.begin();
		ll tsum=0;
		FOR(x,V.size()) {
			ll pt=tsum;
			(tsum+=sum[x])%=mo;
			if(x>=L[i]&&x<R[i]) {
				ll le=V[x]-V[L[i]];
				ll m=V[x+1]-V[x];
				sum[x]=0;
				for(j=i;j>=1;j--) if(dp[x][j]) {
					(sum[x]+=dp[x][j]*(m+le))%=mo;
					(dp[x][j+1]+=dp[x][j]*m)%=mo;
					dp[x][j]=dp[x][j]*le%mo;
				}
				(dp[x][1]+=pt*m)%=mo;
				(sum[x]+=pt*m)%=mo;
			}
			else if(x<L[i] && sum[x]) {
				FOR(j,i+2) dp[x][j]=0;
				sum[x]=0;
			}
			else if(sum[x]) {
				FOR(j,i+2) if(dp[x][j]) (dp[x][j]*=V[R[i]]-V[L[i]])%=mo;
				(sum[x]*=V[R[i]]-V[L[i]])%=mo;
			}
		}
		
	}
	
	ll ret=0;
	FOR(i,V.size()-1) {
		FOR(x,N+1) if(dp[i][x]) {
			ll p=(V[i]+(V[i+1]-V[i])*x%mo*modpow(x+1))%mo;
			(ret+=p*dp[i][x])%=mo;
		}
	}
	for(i=1;i<=N+1;i++) ret=ret*i%mo;
	cout<<ret<<endl;
	
	
}

まとめ

本番、O(N^3)は厳しいかなと思ってO(N^2)やO(N^2*logN)の解法を探してしまい失敗。
O(N^3)で突っ込めばよかったかも。