XVIII Open Cup named after E.V. Pankratiev. Grand Prix of Saratov.

---

复盘人：rxd

开场大家讨论了出了F，是个中期题准备先留着。
大家讨论了下J，叶队说是分治，感觉很对。
gt上机过了A。

0h21min：A(+0)。

我上去写J，第一发交把q打成n了WA了一次。写之前把K题意告诉了gt。

0h34min：J(+1)。

gt告诉我K直接暴力就行了，于是我开始写。写到0h48min的时候换gt上C。

0h58min：C(+0)。
1h15min：K(+0)。

其间gt说L题直接求个最短路径DAG的支配树就行了。我表示这个求下LCA就行了。于是我来写L。
一个fa[0][y]打成fa[y][0]（改的时候漏改了）调了一万年。

1h40min：L(+0)。

gt写D。我找了下F题rho的板子。

2h02min：D(+1)。

我贴了个自己以前的rho板子，本地一测就死循环了。只好翻出Bytedance上的rho板子。（应该抄一遍的，我直接贴了）

2h37min：F(+0)。

叶队差不多这个时候终于放弃了神仙B题。
gt和叶队讨论出了G就是个差分约束，我来写。
第一次写完一交WA 7，后来发现答案可能是实数。
改完一交WA 8，后来发现要把所有的点dis减去dis[s]才是合法方案（固定不动的点被直接当成常量连的边）。

3h12min：G(+2)。

之后gt一直在写I，我想H并讲给叶队。这个题灿爷去年在绍一讲过，我对判叶子还有一点印象。
后来想了出来。gt的I RE之后下机眼调，我上机写H，叶队在一旁监工。配合得还不错。写完调过样例就一发过了。

4h25min：I(+1)。
4h44min：H(+0)。

---

A：

B(by yjn)：当时全部用下降幂撸开推，推得自闭了。最初的形式如果不要写成对所有长度n的排列求期望改成对所有组合求期望会好推很多。总之写几个结论吧。。

把元素可以先都换成平均数，简化推导。

下降幂的和、组合数的和本质是一样的，不要傻了吧唧用Abel再去算下降幂的和了还容易算错……

下降幂乘iter求和，比赛的时候用分部积分推的，转成组合数差分一下会好算很多……

高精度阶乘只能分治fft。下降幂的比值之类的反正到最后都是罗质数然后分治fft。

$(p,q)=(P,Q)=(q,Q)=1$的时候直接分数相加，不用约分。如果$(q,Q)=d$，那么先把$\frac 1 d$拿出来最后$\frac 1 d$和分子去约分。这个是小整数和大整数约分，是线性的。

补题是不可能补题的。

C：

D：

E：Sol(1):考虑每个点的出度和入度都要是1,每条边可以成为一个出度或者一个入度,对二分图用HK算法直接求解似乎就行.

Sol(2):首先所有度数<=1的点可以直接拿掉.现在每个点度数都>=2,那么每次找一个点dfs下去,就一定能找到一组合法解.

F：由于\(k \le n/2\)，最后至少会剩下一半的数。直接随机一个，把所有数跟它的gcd的位置++，然后对它所有约数求个倍数和就可以了。复杂度\(O(S(n^{0.25}+d(n)\omega(n)))\)，$S$是随机次数。附rho板子：

namespace Rho{
	ll Mul(ll x,ll y,const ll z){
		return (x*y-(ll)(((long double)x*y+0.5)/(long double)z)*z+z)%z;
	}
	ll Pow(ll a,ll b,ll p){
		ll res=1;
		for (a%=p;b;b>>=1,a=Mul(a,a,p)) if (b&1) res=Mul(res,a,p);
		return res;
	}
	ll Pow(ll a,ll b){
		ll res=1;
		for (;b;b>>=1,a=a*a) if (b&1) res=res*a;
		return res;
	}
	bool test(ll a,ll n){
		if (a==n) return 1;
		ll k=0,m=n-1;
		for (;~m&1;m>>=1,++k);
		a=Pow(a,m,n);
		for (ll b;k--;a=b){
			b=Mul(a,a,n);
			if (b==1&&a^1&&a!=n-1) return 0;
		}
		return a==1;
	}
	bool ispr(ll n){
		if (n<=1) return 0;
		static int p[]={2,3,5,7,11,13,17,19,23,29,31,37};
		if (n==2) return 1;
		if (n%2==0) return 0;
		For(i,0,12){
			if (!test(p[i],n)) return 0;
		}
		return 1;
	}
	ll ran(){
		return (0ll+rand())<<30|rand();
	}
	vector<ll> decompose(ll n){
		vector<ll> res;
		if (n==1) return res;
		if (ispr(n)){
			res.pb(n);
			return res;
		}
		ll x=ran()%n,c=ran()%n,y=x,k=2,i=1;
		for (;;){
			++i;
			ll g=__gcd(n+y-x,n);
			if (g>1&&g<n){
				vector<ll> a=decompose(g),b=decompose(n/g);
				For(i,0,b.size()) a.pb(b[i]);
				return a;
			}
			if (i==k) k<<=1,y=x;
			x=(Mul(x,x,n)+c)%n;
			if (x==y) break;
		}
		return decompose(n);
	}
	vector<ll> prs(ll n){
		vector<ll> ret=decompose(n);
		sort(ret.begin(),ret.end());
		return ret;
	}
}

G：二分T变成差分约束。固定的点直接当成常数从源点到每个点连边。然后每个点dis设成0开始跑bellman-ford，如果第\(n+1\)轮还有更新就有负环，无解。否则把所有点dis减去dis[s]就是一组合法解。（好像可以把s之外的点设成+inf，dis[s]设成0。这样如果没有负环的话dis[s]最后一定是0，就不用减了）

H：考虑询问全集去掉x，根据答案是n还是n-1可知x是否为叶子。这样100步可以问出叶子集合。由于没有度为2的点，非叶结点最多50个。考虑把第一片叶子作为根，每次加入一片叶子，对于所有非叶结点x，把x、根、它问一遍可以得到根到这片叶子路径上的点的集合。动态地把边分裂下去，维护下这棵树的形态就可以了。询问次数最大就是100+49*50=2550.

I：对所有的子串建出缩边后的串就可以直接树形dp了.建trie就直接把所有的串排序,用ST表维护high数组,复杂度\(O(N \log N)\)

J：直接线段树的话是\(O(q \log n*20^2)\)的。如果模数比较好的话可以DFT，这样是\(O(q(\log n+20))\)的。如果模数不好可以用double倍增DFT再取模。复杂度\(O(q \log n*20)\)。事实上直接分治，这样处理前缀后缀信息的时候都只有单点加。复杂度是\(O(q \log n*20)\)。

K：线段树合并搞出每个节点的Right集合，然后直接暴力往后爬.

upd by fz:对于一次长度为i的询问,至多会访问n/i个串,那么最坏情况是询问1,2,2,3,3,3....的情况.询问总数大概为\(O(N^{4/3})\).

L：搞出最短路径图，是个DAG，然后每条边中间塞一个点，就变成了求支配树。DAG上的支配树，一个点的父亲就是所有到它的点在支配树上的LCA。