[NOI2017] 整数，蚯蚓排队，泳池

前言

本来只是想写一下[NOI2017] 泳池的题解，不过前两题题解太短了干脆挼一起了。

[NOI2017] 整数

考虑大力数据结构，直接开一个长度为 $30n+233$（或者+114514） 的线段树，用最朴素的方法维护每个bit的值。

加上一个正整数 $a$ 可以直接把序列上对应位置长为 $\log a$ 的那一段数拿下来做加法，然后把前 $\log a$ 位再贴回去。最后考虑和的第 $\log a+1$ 位，最多进位为1，我们找到序列上前面第一个0的位置然后做一个区间取反即可。

减法类似，若需要补位则找前面第一个1的位置即可。

复杂度 $O(n(\log n+\log a))$，理论上常数较大，但是用zkw线段树可以轻松进900ms。

#include//JZM yyds!!
#define ll long long
#define lll __int128
#define uns unsigned
#define fi first
#define se second
#define IF (it->fi)
#define IS (it->se)
#define END putchar('\n')
#define lowbit(x) ((x)&-(x))
#define inline jzmyyds
using namespace std;
const int MAXN=1e6+5;
const ll INF=1e18;
ll read(){
	ll x=0;bool f=1;char s=getchar();
	while((s<'0'||s>'9')&&s>0){if(s=='-')f^=1;s=getchar();}
	while(s>='0'&&s<='9')x=(x<<1)+(x<<3)+(s^48),s=getchar();
	return f?x:-x;
}
int ptf[50],lpt;
void print(ll x,char c='\n'){
	if(x<0)putchar('-'),x=-x;
	ptf[lpt=1]=x%10;
	while(x>9)x/=10,ptf[++lpt]=x%10;
	while(lpt>0)putchar(ptf[lpt--]^48);
	if(c>0)putchar(c);
}
const int MAXM=1<<25|(MAXN<<5);
int n,m;
struct zkw{
	bool f[MAXM],h[MAXM],lz[MAXM];
	int p,dep;
	void init(int n){for(p=1,dep=0;p<n+2;p<<=1,dep++);}
	void cover(int x,bool e){f[x]=h[x]=e,lz[x]=1;}
	void upd(int x){f[x]=f[x<<1]&f[x<<1|1],h[x]=h[x<<1]|h[x<<1|1];}
	void pushd(int x){
		if(lz[x]){
			f[x<<1]=f[x<<1|1]=h[x<<1]=h[x<<1|1]=f[x];
			lz[x<<1]=lz[x<<1|1]=1,lz[x]=0;
		}
	}
	void add(int l,int r,bool e){
		l=p^(l-1),r=p^(r+1);
		for(int i=dep;i>0;i--)pushd(l>>i),pushd(r>>i);
		while(l^1^r){
			if(~l&1)cover(l^1,e);
			if(r&1)cover(r^1,e);
			l>>=1,r>>=1,upd(l),upd(r);
		}for(l>>=1;l;l>>=1)upd(l);
	}
	uns ll query(int l,int r){
		l^=p,r^=p;
		for(int i=dep;i>0;i--)
			for(int j=l>>i,lm=r>>i;j<=lm;j++)pushd(j);
		uns ll res=0;
		for(int i=r;i>=l;i--)res=res<<1|f[i];
		return res;
	}
	void fz(int l,int r,uns ll d){
		l^=p,r^=p;
		for(int i=dep;i>0;i--)
			for(int j=l>>i,lm=r>>i;j<=lm;j++)pushd(j);
		for(int i=l;i<=r;i++,d>>=1)f[i]=h[i]=d&1;
		for(l>>=1,r>>=1;l;l>>=1,r>>=1)
			for(int j=l;j<=r;j++)upd(j);
	}
	int sch0(int l){
		for(int i=(l^=p,dep);i>0;i--)pushd(l>>i);
		for(;l>1;l>>=1)if((~l&1)&&!f[l^1]){l^=1;break;}
		for(;l<p;pushd(l),l<<=1,l^=f[l]);
		return l^p;
	}
	int sch1(int l){
		for(int i=(l^=p,dep);i>0;i--)pushd(l>>i);
		for(;l>1;l>>=1)if((~l&1)&&h[l^1]){l^=1;break;}
		for(;l<p;pushd(l),l<<=1,l^=!h[l]);
		return l^p;
	}
	void chg(int x,bool e){
		x^=p;
		for(int i=dep;i>0;i--)pushd(x>>i);
		f[x]=h[x]=e;
		for(int siz=(x>>=1,1);x;x>>=1,siz<<=1)upd(x);
	}
	bool sch(int x){
		x^=p;
		for(int i=dep;i>0;i--)pushd(x>>i);
		return f[x];
	}
}T;
int main()
{
	m=read(),read(),read(),read();
	n=m*30+233,T.init(n);
	for(int id=1;id<=m;id++){
		int op=read();
		if(op==1){
			ll a=read();
			int l=read()+1,r=l+29;
			if(a==0)continue;
			ll b=T.query(l,r),mx=1ll<<30;
			T.fz(l,r,(a+b+mx)&(mx-1));
			if(a+b>=mx){
				int c=T.sch0(r);
				if(c>r+1)T.add(r+1,c-1,0);
				T.chg(c,1);
			}else if(a+b<0){
				int c=T.sch1(r);
				if(c>r+1)T.add(r+1,c-1,1);
				T.chg(c,0);
			}
		}else print(T.sch(read()+1));
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116

[NOI2017] 蚯蚓排队

这题没啥好说的，直接维护链表+Hash即可。

代码我没写，看粪兔的。

[NOI2017] 泳池

看到这个“面积最大值恰好为 $k$”，可以很自然地转化为“面积都不超过 $k$”减去“面积都不超过 $k-1$”。

考虑怎么求矩形面积不超过 $k$ 的概率。我们知道一种求最大矩形面积的方法是把每个位置从岸边出发的最长安全距离弄成整数序列，然后用笛卡尔树，所以可以类似地定义一个区间DP来求。由于每个位置等价，所以直接设状态为区间长度：

令 $dp[i][j]$ 表示长度为 $i$ 的区间，区间最小值为 $j$ 的概率，我们只需要满足 $i\times j\le k$，转移就直接枚举第一个取到最小值的位置，用一下后缀和优化即可。这里我们只需要考虑最小值 $>0$ 的区间，所以区间长度不超过 $k$。

注意到状态总数是 ${\sum }_{i=1}^k\frac{k}{i}=k\log k$，且转移总复杂度为 $O({\sum }_{i=1}^k\frac{k}{i}\cdot i)=O(k^2)$ 可以通过。

显然整个序列被值为0的位置划分成了若干段，我们需要对每种划分组合的概率求和。

遇到划分计数的问题又不得不用到生成函数了。设 $f(x)={\sum }_{i=1}^{k+1}({\sum }_{j>0}dp[i-1][j])\cdot (1-q)x^i$ 表示每种长度的非0区间后跟一个0的概率的生成函数，那么
$$Ans=\frac{1}{1-q}[x^{n+1}]\left(1+f(x)+f^2(x)+...\right)=\frac{1}{1-q}[x^{n+1}]\frac{1}{1-f(x)}$$还剩下一个求多项式分式 $\frac{1}{1-f(x)}$ 远项的问题，用波斯坦-茉莉算法即可。

多项式长度 $O(k)$，所以可以暴力卷积。

#include//JZM yyds!!
#define ll long long
#define lll __int128
#define uns unsigned
#define fi first
#define se second
#define IF (it->fi)
#define IS (it->se)
#define END putchar('\n')
#define lowbit(x) ((x)&-(x))
#define inline jzmyyds
using namespace std;
const int MAXN=1e3+10;
const ll INF=1e18;
ll read(){
	ll x=0;bool f=1;char s=getchar();
	while((s<'0'||s>'9')&&s>0){if(s=='-')f^=1;s=getchar();}
	while(s>='0'&&s<='9')x=(x<<1)+(x<<3)+(s^48),s=getchar();
	return f?x:-x;
}
int ptf[50],lpt;
void print(ll x,char c='\n'){
	if(x<0)putchar('-'),x=-x;
	ptf[lpt=1]=x%10;
	while(x>9)x/=10,ptf[++lpt]=x%10;
	while(lpt>0)putchar(ptf[lpt--]^48);
	if(c>0)putchar(c);
}
const ll MOD=998244353;
ll ksm(ll a,ll b,const ll&mo=MOD){
	ll res=1;
	for(;b;b>>=1,a=a*a%mo)if(b&1)res=res*a%mo;
	return res;
}
ll n,p[MAXN],dp[MAXN][MAXN],P[MAXN],Q[MAXN],f[MAXN<<1];
int k;
ll solve(int m){
	if(m<0)return 0;
	if(!m)return ksm(p[0],n);
	memset(dp,0,sizeof(dp));
	for(int i=0;i<=m+1;i++)dp[0][i]=1;
	for(int i=1;i<=m;i++)
		for(int j=m/i;j>=0;j--){
			ll&f=dp[i][j];
			for(int k=1;k<=i;k++)
				(f+=dp[k-1][j+1]*p[j]%MOD*dp[i-k][j])%=MOD;
			(f+=dp[i][j+1])%=MOD;
		}
	memset(P,0,sizeof(P));
	memset(Q,0,sizeof(Q));
	P[0]=Q[0]=1;
	for(int i=1;i<=m+1;i++)Q[i]=dp[i-1][1]*(MOD-p[0])%MOD;
	for(int N=n+1;N;N>>=1){
		for(int i=0;i<=(m+2)<<1;i++)f[i]=0;
		for(int i=0;i<=m+1;i++)
			for(int j=0;j<=m+1;j++)
				(f[i+j]+=P[i]*((j&1)?MOD-Q[j]:Q[j]))%=MOD;
		for(int i=0;i<=m+1;i++)P[i]=f[i<<1|(N&1)];
		for(int i=0;i<=(m+2)<<1;i++)f[i]=0;
		for(int i=0;i<=m+1;i++)
			for(int j=0;j<=m+1;j++)
				(f[i+j]+=Q[i]*((j&1)?MOD-Q[j]:Q[j]))%=MOD;
		for(int i=0;i<=m+1;i++)Q[i]=f[i<<1];
	}return P[0]*ksm(Q[0]*p[0]%MOD,MOD-2)%MOD;
}
int main()
{
	n=read(),k=read(),p[0]=read();
	p[0]=(MOD+1-ksm(read(),MOD-2)*p[0]%MOD)%MOD;
	for(int i=1;i<=k;i++)p[i]=ksm(MOD+1-p[0],i)*p[0]%MOD;
	print((solve(k)-solve(k-1)+MOD)%MOD);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73