T1 嗑瓜子

因为我几天前做了一道期望题，那个题是数据范围也是比较小，而且正解是\(o(n)\)的，所以这道题我也就一直在想\(o(n)\)的做法，想了一个多小时，没什么思路，就直接弃了。但是正解是\(o(n^2)\)的。
刚开始我设\(f_{i,j}\)表示我拿了\(i\)个瓜子，\(j\)个瓜子皮的期望次数，但是得到的结果不对，然后根据定义显然没法转移，因为我拿\(i\)个瓜子，\(j\)个瓜子皮的期望次数显然就是\(i+j\)次，所以这样正推不可行。
于是设\(f_{i,j}\)表示目前还剩\(i\)个瓜子，\(j\)个瓜子皮的期望次数，那么转移方程显然就是\(f_{i,j}= \frac{j}{i+j}f_{i,j-1}+\frac{i}{i+j}f_{i-1,j+2}\).
最后还有注意的一点，题目要求输出\(q\times r\)与\(p\)同余，那么也就是\(r\)与\(\frac{p}{q}\)同余，也就是\(p\times inv[q]\)

代码如下：

AC_code



#include<bits/stdc++.h>
#define int long long
#define re register int
#define ii inline int
#define iv inline void
using namespace std;
const int mo=998244353;
const int N=2e3+10;
const int M=1e4+10;
int n,ans;
int f[N][N<<1],jc[M],pv[M],inv[M];
ii read()
{
	int x=0; char ch=getchar(); bool f=1;
	while(ch<'0' or ch>'9')
	{
		if(ch=='-') f=0;
		ch=getchar();
	}
	while(ch>='0' and ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return f?x:(-x);
}
ii ksm(int d,int z)
{
	int out=1;
	while(z)
	{
		if(z&1) out=out*d%mo;
		z>>=1;
		d=d*d%mo;
	}
	return out;
}
signed main()
{
	freopen("eat.in","r",stdin);
	freopen("eat.out","w",stdout);
	n=read();
	if(n==1) {printf("1\n");return 0;}
	jc[0]=1;
	for(re i=1;i<M;i++) jc[i]=jc[i-1]*i%mo;
	pv[M-1]=ksm(jc[M-1],mo-2);
	for(re i=M-2;i>=0;i--) pv[i]=pv[i+1]*(i+1)%mo;
	inv[0]=1;
	for(re i=1;i<M;i++) inv[i]=pv[i]*jc[i-1]%mo;
	for(re i=1;i<=n;i++) for(re j=0;j<=(n-i)*2;j++) f[i][j]=(j*inv[i+j]%mo*f[i][j-1]%mo+i*inv[i+j]%mo*f[i-1][j+2]%mo+1ll)%mo;
	printf("%lld\n",f[n][0]);
	return 0;
}

T2 第k大查询

思路：
如果我们找到朝左和朝右k个比它大的元素，那么一个个元素是第\(k\)当且仅当个包含了\(k-1\) 个比它大的元素，可以在\(o(k)\) 时间复杂度内解决。如何找到往左往右比它大的\(k\)个元素，我们可以把元素用双向链表连接起来，每次删除一个元素的时候往左往右找即可。

代码如下：

AC_code



#include<bits/stdc++.h>
#define int long long
#define re register int
#define ii inline int
#define iv inline void
using namespace std;
const int N=5e5+10;
int n,k,ans;
int pre[N],suf[N];
int a[N],pos[N],u1[N],u2[N];
ii read()
{
	int x=0; char ch=getchar(); bool f=1;
	while(ch<'0' or ch>'9')
	{
		if(ch=='-') f=0;
		ch=getchar();
	}
	while(ch>='0' and ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return f?x:(-x);
}
signed main()
{
	freopen("kth.in","r",stdin);
	freopen("kth.out","w",stdout);
	n=read(),k=read();
	for(re i=1;i<=n;i++) a[i]=read(),pos[a[i]]=i;
	int p=pos[1];
	for(re i=1;i<=n;i++) pre[i]=i-1,suf[i]=i+1;
	for(re i=1;i<=n;i++)
	{
		int l=0,r=0;
		for(re j=pos[i];j and l<k;j=pre[j]) u1[l++]=j-pre[j];
		for(re j=pos[i];j<=n and r<k;j=suf[j]) u2[r++]=suf[j]-j;
		for(re j=0;j<l;j++) if(k-j-1<r) ans=ans+i*u1[j]*u2[k-j-1];
		suf[pre[pos[i]]]=suf[pos[i]];
		pre[suf[pos[i]]]=pre[pos[i]];
		pre[pos[i]]=suf[pos[i]]=0;
	}
	printf("%lld\n",ans);	
	return 0;
}