PKUSC2019
准备很匆忙，再次体验了下OI的快乐

n个随机实数的第k小的期望

下面我们只讨论在[0,1]间随机的情况，其他直接放缩就好了

众所周知最大可以直接积分，最小翻转一下，今天看到地震后的幻想乡，发现k任意也可以求

有两种方法：A,B

B比较简单先说B，就是 $\sum_{all} \frac{1}{all} a_{p_k}=\sum_{all} \frac{1}{all} [变量s \leq a_{p_k}]$

将所有点取值情况投影到数轴，对于某种投影，共$(n+1)!$种情况，有 $i \times n!$ 种合法，即 $\frac{i}{n+1}$

注意到每种投影的概率不同，但因为权值相同，所以没有影响

A先挖个坑，没有细看，复合函数积分碰到的话回来看看

PKUWC2019D1T2口胡

注意到树的并也是树，既然是树的计数考虑点-边，以点为例

考虑求出每个点被多少棵虚树包含（$col_x$），这个可以差分，用些小技巧让虚树上每个点的系数=1

那么 $ans_i=\sum_x C_{col_x}^i=\frac{1}{i!}\sum_{j=i}^n \frac{tot_j j!}{(j-i)!}$ 这个翻转一下ntt优化即可

CF1146F Leaf Partition

一开始的想法是f(x,0/1)表示x这个点当前已占用或钦定后面占用，但似乎后面没法确保被合并掉

换个角度，设0/1表示x向上这条变是否会被使用

实现的时候，f为0，g为1
$$
f(x)=f(x)f(y)+g(x)g(y)\\
tt(x)=\prod f(y) \\
g(x)=g(x)g(y)+g(x)f(y)+tt(x)g(y)
$$
g的转移用tt是因为f中，可能节点x已经被占用

时间复杂度为线性

#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
using namespace std;
namespace mine
{
	typedef long long ll;
	//#define double long double
	const int INF=0x3f3f3f3f;
	const ll LLINF=0x3f3f3f3f3f3f3f3fll;
	ll qread()
	{
		ll ans=0;char c=getchar();int f=1;
		while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
		while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
		return ans*f;
	}
	void write(ll num)
	{
		if(num<0) {num=-num;putchar('-');}
		if(num>9) write(num/10);
		putchar('0'+num%10);
	}
	void write1(ll num){write(num);putchar(' ');}
	void write2(ll num){write(num);puts("");}
	#define FR first
	#define SE second
	#define MP make_pair
	#define pr pair<int,int>
	#define PB push_back
	#define vc vector
	void chmax(int &x,const ll y) {x=(x>y?x:y);}
	void chmin(int &x,const ll y) {x=(x<y?x:y);}
	const ll MOD=998244353;
	void add(int &x,int y){x+=y;if(x>=MOD) x-=MOD;if(x<0) x+=MOD;}
	ll qpower(ll x,int e)
	{
		ll ans=1;
		while(e)
		{
			if(e&1) ans=ans*x%MOD;
			x=x*x%MOD;e>>=1;
		}
		return ans;
	}
	ll inv(ll x){return qpower(x,MOD-2);}
	const int MAX_N=2e5+10;
	vc<int> son[MAX_N];
	ll f[MAX_N],g[MAX_N],tt[MAX_N];//这个点是否被用到 
	void dp(int x)
	{
		tt[x]=1;
		if(son[x].size()==0) f[x]=g[x]=1;
		for(int t=0;t<(int)son[x].size();t++)
		{
			int y=son[x][t];dp(y);
			if(t==0) f[x]=tt[x]=f[y],g[x]=g[y];
			else
			{
				ll ff=f[x]*f[y]+g[x]*g[y];ff%=MOD;
				ll gg=g[x]*g[y]%MOD+g[x]*f[y]%MOD+tt[x]*g[y]%MOD;gg%=MOD;
				f[x]=ff,g[x]=gg;tt[x]=tt[x]*f[y]%MOD;
			}
		}
	}
	void main()
	{
		int n=qread();for(int x=2;x<=n;x++){int fa=qread();son[fa].PB(x);}
		dp(1);write(f[1]);
	}
};
signed main()
{
	srand(time(0));
	mine::main();
}

地震后的幻想乡

一开始考虑排名的期望做的，但太菜了似乎没搞出来；还有就是下述状压用到经典的【考虑集合内编号最小节点所在联通块】

众所周知，一个图的最小生成树具有【最大边权最小】的特性，所以最大边的期望=【最小的，只需要比这个更小的边就能让图联通】的期望

然后期望这东西众所周知是可以转化为概率密度函数前缀和的，即求 $\int_0^1 P(t)，P(t)为只使用t以内的边不连通的概率$
$$
f(S,t)=\sum (1-f(SS,t))(1-t)^{cnt=SS与S-SS间的边数} \\
\int_0^1 f(S,t)dt=\sum \int_0^1 (1-f(SS,t))(1-t)^{cnt}dt=\sum \frac{1}{1+cnt}-\int_0^1 f(SS,t)(1-t)^{cnt}dt \\
同理\int_0^1 (1-t)^Tf(S,t)dt=\sum \frac{1}{1+T+cnt}-\int_0^1 f(SS,t)(1-t)^{T+cnt}dt \\
$$
于是就可以dp了，设 $g(S,T) ，符号意思如上，g(S,T)=\sum \frac{1}{1+T+cnt}-g(SS,T+cnt),ans=g(all,0)$

时间复杂度为 $O(3^nn^2)$

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<algorithm>
using namespace std;
int qread()
{
	int num=0;char c=getchar();
	while(c<'0' or c>'9') c=getchar();
	while('0'<=c and c<='9') num=num*10+c-'0',c=getchar();
	return num;
}
const int MAX_N=12,MAX_M=110;
int bin[MAX_N],siz[1<<MAX_N],mark[MAX_N];
double g[1<<MAX_N][MAX_M];
int main()
{
	bin[0]=1;for(int i=1;i<MAX_N;i++) bin[i]=bin[i-1]<<1;
	for(int i=1;i<bin[MAX_N-1];i++) siz[i]=siz[i>>1]+(i&1);
	
	int n=qread(),m=qread();
	for(int i=1;i<=m;i++)
	{
		int x=qread()-1,y=qread()-1;
		mark[x]|=bin[y];mark[y]|=bin[x];
	}
	for(int T=m;T>=0;T--)
		for(int S=1;S<bin[n];S++) 
		{
			int mi=(S&-S),wt=S^mi;if(S==mi) continue;
			for(int SS=(wt-1)&wt;SS>=0;SS=(SS-1)&wt)
			{
				int a=mi^SS,b=S^a,cnt=0;
				for(int i=0;i<n;i++) if(a&bin[i]) cnt+=siz[mark[i]&b];
				if(T+cnt<=m) g[S][T]+=1.0/(1+T+cnt)-g[a][T+cnt];
				if(SS==0) break;
			}
		}
	printf("%.6lf",g[bin[n]-1][0]);
}

PKUSC2018真实排名

细节：ai相同、=0（特判）

若x不变，则 $[x/2,x)不变，ans=C_{all-cnt-1}^k$

若x变，则 $[x,2x)变，ans=C_{all-cnt}^{k-cnt}$

#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<vector>
#include<algorithm>
using namespace std;
int qread()
{
	int num=0;char c=getchar();
	while(c<'0' or c>'9') c=getchar();
	while('0'<=c and c<='9') num=num*10+c-'0',c=getchar();
	return num;
}
#define MP make_pair
typedef long long ll;
const int MOD=998244353;
const int MAX_N=1e5+10;
ll fac[MAX_N],inv[MAX_N],facinv[MAX_N];
ll C(int n,int m){if(n<m or m<0)return 0;return fac[n]*facinv[m]%MOD*facinv[n-m]%MOD;}
int a[MAX_N],b[MAX_N];
int main()
{
	fac[0]=1;for(int i=1;i<MAX_N;i++) fac[i]=fac[i-1]*i%MOD;
	inv[1]=1;for(int i=2;i<MAX_N;i++) inv[i]=ll(MOD-MOD/i)*inv[MOD%i]%MOD;
	facinv[0]=1;for(int i=1;i<MAX_N;i++) facinv[i]=facinv[i-1]*inv[i]%MOD;
	
	int n=qread(),k=qread();
	for(int i=1;i<=n;i++) a[i]=b[i]=qread();
	sort(b+1,b+n+1);
	for(int i=1;i<=n;i++)
	{
		int ans=0,x=a[i];
		if(x==0) ans=C(n,k);
		else
		{
			int aa=lower_bound(b+1,b+n+1,x)-1-lower_bound(b+1,b+n+1,(int)ceil(x/2.0))+1;
			int bb=lower_bound(b+1,b+n+1,2*x)-1-lower_bound(b+1,b+n+1,x)+1;
			ans=C(n-aa-1,k)+C(n-bb,k-bb);
		}
		printf("%d\n",(ans%MOD+MOD)%MOD);
	}
}

Day1

t1明显就是在直接逆序对的基础上改了改（题意修正=强烈暗示），时间倒流+启发式合并+主席树就好了，$O(nlog^2n)$

t2花了很久debug假做法，然后爽快一分没有

正解的压法挺不错，对于每个数，把它小的设为0，大的设为1，那么状态为 $3^n$

然后只有01的情况需要枚举0/1，复杂度应该是 $O(n^2m4^n)$

t3还不会

Day2

t1应该会47分，但太难写了（3个代码）就没有写，玩了玩t3感觉不好搞就跑路了

然后就玩了一整场t2，先把菊花写了，然后二叉树玩半天终于发现了一种有解策略，因为不知道有没有更优的情况所以就先写了，gg后又玩了半天，从数轴开始逐步考虑，把二叉树的做法搞出来了（把dfs换成bfs），此时剩1.7h；然后此时回去看看t1发现还是不会，有点小难受，然后这个t2我不知道为什么做法不能拓展到正解，想半天觉得应该是插入顺序什么的，瞎jb试了各种方法都不行，不太会理性分析，于是就滚粗了

人生即使不能走最短路，仍是连通图

PKUSC2019前后