ARC126 F Affine Sort

被两年前的 zhy 爆杀了 QwQ。

对于题目中的极限式，有如下事实：

Stolz 定理

当 \(g\) 是严格单调且趋近于无穷的数列时，有：

\[\lim_{n\to \infin} \frac{f_n}{g_n}=\lim_{n\to \infin} \frac{f_n-f_{n-1}}{g_n-g_{n-1}} \]

所以：

注意到 \(f(n)-f(n-1)\) 相当于钦定 \(c=n\) 的贡献，我们现在要算当 \(c\to \infin\) 时的答案。

当 \(c\) 趋近于无穷时，\(a,b\) 的取值越来越接近 \([0,c)\) 上的均匀分布。我们直接去考虑 \(a'=\frac{a}{c},b'=\frac{b}{c}\)，答案只和这两个值有关，而且它们可以看成 \([0,1)\) 上的均匀随机变量。这就成了一道概率题了。

我们可以将一根 \([0,1)\) 的数轴首尾相接，那么原来的 \(aX_i+b\bmod c\) 可以看成第 \(i\) 个点以 \(X_i\) 的速度在这个环上走 \(a'\) 秒，然后再将整个环旋转 \(b'\) 单位长度。

最后的旋转相当于是说如果所有点移动结束后 \(1\sim n\) 以顺时针顺序排列，那么最终数组有序的概率就是点 \(1\) 与点 \(n\) 的距离。如果知道了合法的时间区间积分就做完了。

现在只要求所有点以顺时针顺序排列的概率。一种方法是求出所有点对相碰的时间暴力模拟整个过程，显然会 T。

我们可以考虑到求出相邻点有向距离之和，当且仅当恰好等于 \(1\) 时所有点以顺时针顺序排列。

容易发现相邻点有向距离的变性点只有 \(O(\sum X_i)\) 个。于是直接模拟，复杂度 \(O(\sum X_i\log \sum X_i)\)。

#include <cstdio>
#include <algorithm>
using namespace std;
int read(){/*...*/}
const int N=1003,M=1000003,P=998244353;
typedef long long ll;
int n,cur,rk;
int a[N],b[N];
struct Event{
	int t,d,x;
	friend bool operator<(const Event u,const Event v){
		return (ll)u.t*v.d<(ll)v.t*u.d;
	}
}s[M];
int inv[M];
ll res;
void calc(int l,int r){
	int pp=((ll)r*r-(ll)l*l)%P;
	if(pp<0) pp+=P;
	if(pp&1) pp+=P;
	pp>>=1;
	res=(res+(ll)pp*(a[1]-a[0])+(ll)b[1]*(r-l))%P;
}
int main(){
	n=read();
	for(int i=1;i<=n;++i) a[i]=read();
	inv[1]=1;
	for(int i=2;i<M;++i) inv[i]=(ll)inv[P%i]*(P-P/i)%P;
	a[0]=a[n];
	for(int i=1;i<=n;++i){
		int dlt=a[i]-a[i-1];
		if(dlt<0){dlt=-dlt;++b[i];++cur;}
		for(int p=1;p<dlt;++p)
			s[++rk]=(Event){p,dlt,i};
	}
	sort(s+1,s+rk+1);
	int las=0;
	for(int i=1;i<=rk;++i){
		int cc=(ll)s[i].t*inv[s[i].d]%P;
		if(cur==1) calc(las,cc);
		las=cc;
		int x=s[i].x;
		if(a[x]>a[x-1]) --b[x],--cur;
		else ++b[x],++cur;
	}
	if(cur==1) calc(las,1);
	if(res<0) res+=P;
	while(res%3) res+=P;
	res/=3;
	printf("%d\n",int(res));
	return 0;
}

ARC125 F

由 Prufer 序我们知道只要 \(\sum deg_i=2n-2,deg_i\geq 1\) 啥树都能构造出来的。

于是我们将 \(deg_i\) 都减去 \(1\) 然后打表打出所有的 \((x,y)\)，发现它竖着的 \(1\) 一定是一段区间？？？

于是对每种值记录一个选取个数的区间，将相同的 \(deg\) 压在一起多重背包。\(O(n\sqrt n)\) 。

#include <cstdio>
#pragma GCC optimize(2,3,"Ofast")
using namespace std;
int read(){/*...*/}
const int N=400003,INF=0x3f3f3f3f;
int f[N],g[N],_f[N],_g[N];
int n,sm,d[N],cnt[N];
int qf[N],hdf,tlf;
int qg[N],hdg,tlg;
int main(){
	n=read();
	for(int i=1;i<n;++i) ++d[read()],++d[read()];
	for(int i=1;i<=n;++i) ++cnt[--d[i]],f[i]=INF,g[i]=-INF;
	f[0]=0;g[0]=cnt[0];
	for(int x=1;x<n;++x){
		if(!cnt[x]) continue;
		for(int i=0;i<=sm;++i) _f[i]=f[i]-i/x,_g[i]=g[i]-i/x,f[i]=INF,g[i]=-INF;
		int px=x*cnt[x];
		int tsm=sm+px;
		for(int t=0;t<x;++t){
			hdf=hdg=1;tlf=tlg=0;
			for(int i=t;i<=tsm;i+=x){
				if(i<=sm){
					while(hdf<=tlf&&_f[qf[tlf]]>=_f[i]) --tlf;
					while(hdg<=tlg&&_g[qg[tlg]]<=_g[i]) --tlg;
					qf[++tlf]=qg[++tlg]=i;
				}
				while(hdf<=tlf&&qf[hdf]<i-px) ++hdf;
				while(hdg<=tlg&&qg[hdg]<i-px) ++hdg;
				if(hdf<=tlf) f[i]=_f[qf[hdf]]+i/x;
				if(hdg<=tlg) g[i]=_g[qg[hdg]]+i/x;
			}
		}
		sm=tsm;
	}
	long long res=0;
	for(int i=0;i<=sm;++i)
		if(f[i]<=g[i]) res+=g[i]-f[i]+1;
	printf("%lld\n",res);
	return 0;
}