Luogu P3600 随机数生成器

题目描述

sol研发了一个神奇的随机数系统，可以自动按照环境噪音生成真·随机数。

现在sol打算生成(n)个([1,x])的整数(a_1...a_n)，然后进行一些询问。

(q)次询问，每次询问i有两个参数(li)和(ri)，sol会计算(min_{li leq j leq ri} a_j)（a数组中下标在(li、ri)之间的数的最小值）。

最后测试结果会是这些询问得到的结果的最大值。

sol进行了很多次实验，现在他想问问你测试结果的期望大小是多少，对(666623333)取模。

输入输出格式

输入格式：

第一行三个数(n、x、q)。

下面q行，第i行两个数表示(li)和(ri)。

输出格式：

一行一个数，表示答案。

输入输出样例

输入样例#1：

2 2 1
1 2

输出样例#1：

499967501

输入样例#2：

6 6 6
1 3
2 4
3 5
4 6
5 6
3 4

输出样例#2：

88571635

根据整数期望公式：

因为是所有的最小值取最大值，所以(p(X<i))比(p(Xgeq i))好求一些。

我们考虑对每个(i)分别求。

合法情况要求询问的每个区间中至少有一个(<i)的数。如果两个区间有包含关系，很明显大的区间没有用。将剩余的区间按左端点排序后，对于坐标上的每个点，包含它的区间的编号一定是连续的。所以我们将问题转换：有很多区间，选择一个区间的概率为(P)，要选择一些区间将整个坐标轴覆盖，问概率。

很明显这些区间的左右端点都是单调不下降的（去掉无用区间）。设(f_i)表示最后一个选择的区间为(i)，并且将(r_i)以及之前的坐标都覆盖了的概率。

前缀和优化一下单次(DP)就可以做到(O(n))了。

代码：

#include<bits/stdc++.h>
#define ll long long
#define N 2005

using namespace std;
inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}

const ll mod=666623333;
ll ksm(ll t,ll x) {
	ll ans=1;
	for(;x;x>>=1,t=t*t%mod)
		if(x&1) ans=ans*t%mod;
	return ans;
}

int n,x,m;
struct interval {
	int l,r;
	bool operator <(const interval &a)const {
		if(l!=a.l) return l<a.l;
		return r>a.r;
	}
}s[N];

interval st[N];
int top;

int L[N],R[N];
ll ans;
ll DP(ll p) {
	if(p==1) return 1;
	static ll f[N],pw[N],inv[N];
	memset(f,0,sizeof(f));
	
	pw[0]=inv[0]=1;
	for(int i=1;i<=n;i++) pw[i]=pw[i-1]*(mod+1-p)%mod;
	inv[1]=ksm(mod+1-p,mod-2);
	for(int i=2;i<=n;i++) inv[i]=inv[i-1]*inv[1]%mod;
	f[0]=1;
	int lx=0,rx=0;
	ll sum=1;
	for(int i=1;i<=n;i++) {
		while(lx<=i&&R[lx]<L[i]-1) {
			sum=(sum-f[lx]*inv[lx]%mod+mod)%mod;
			lx++;
		}
		while(rx+1<i&&R[rx+1]>=L[i]-1) {
			sum=(sum+f[rx+1]*inv[rx+1])%mod;
			rx++;
		}
		f[i]=sum*p%mod*pw[i-1]%mod;
	}
	ll ans=0;
	for(int i=1;i<=n;i++) {
		if(R[i]==m) (ans+=f[i]*pw[n-i])%=mod;
	}
	return ans;
}

int main() {
	n=Get(),x=Get(),m=Get();
	for(int i=1;i<=m;i++) s[i].l=Get(),s[i].r=Get();
	sort(s+1,s+1+m);
	for(int i=1;i<=m;i++) {
		while(top>=1&&st[top].r>=s[i].r) top--;
		st[++top]=s[i];
	}
	
	m=top;
	for(int i=1;i<=m;i++) s[i]=st[i];
	
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=m;j++) if(s[j].l<=i&&i<=s[j].r) R[i]=j;
		for(int j=m;j>=1;j--) if(s[j].l<=i&&i<=s[j].r) L[i]=j;
	}
	top=0;
	for(int i=1;i<=n;i++) {
		if(L[i]&&R[i]) L[++top]=L[i],R[top]=R[i];
	}
	n=top;
	ll invx=ksm(x,mod-2);
	for(int i=1;i<=x;i++) {
		(ans+=mod+1-DP((i-1)*invx%mod))%=mod;
	}
	cout<<ans;
	return 0;
}