蜜月日记 Part10 - 洛谷仓库

前言

Day 100 最后冲刺！

Day 91

由于原本这一天的题过于简单了且没有技巧所以换掉。

神秘线代科技。

2025/06/30 [PA 2022] Drzewa rozpinające

题意

给定一个长为

n

的序列

a_1,\cdots,a_n

。有

n

个点，第

i

个点和第

j

个点之间连了

\gcd(a_i,a_j)

条边，求这张图的生成树个数对

10^9+7

取模的值。

思路

设值域为

m

。

先回忆一下无向图矩阵树定理。设

D

为度数矩阵去掉最后一行最后一列，

G

为邻接矩阵去掉最后一行最后一列，则生成树个数为

\det(D-G)

。

直接计算就

O(n^3)

了显然是跑不过的。我们需要用行列式的性质化简。

事实上，我们有：

【矩阵行列式引理】 对于

n\times n

的可逆矩阵

A

和

n\times m

的矩阵

U,V

，有

\det(A+UV^{\top})=\det A\det(I+V^{\top}A^{-1}U)

。

如果

A

的行列式好算（比如对角矩阵），且

\det(I+V^{\top}A^{-1}U)

更好算（比如

m<<n

时）可以用矩阵行列式引理来算。

回到矩阵树定理。发现这个定理的形式就是给我们用这个的。我们要求

\det(D-G)

，其中

D

是对角矩阵行列式好算，只需要找到合适的

U,V

即可。

观察

G

的结构，我们有

G_{i,j}=\gcd(a_i,a_j)=\sum\limits_{d|a_i,d|a_j}\varphi(d)=\sum\limits_{d=1}^m[d|a_i]\varphi(d)[d|a_j]

。

于是构造

(n-1)\times m

的矩阵

U,V

，其中

U_{i,d}=[d|a_i]\varphi(d),V_{i,d}=[d|a_j]

，则

G=UV^{\top}

。

那么

(I-V^{\top}D^{-1}U)_{i,j}=[i=j]-\varphi(j)\sum\limits_{t=1}^{n-1}[i|a_t][j|a_t]

。这个只在

\operatorname{lcm}(i,j)\le m

的时候有值。

每次只消元有值的位置，复杂度能过。不能过把矩阵转置一下就过了。

代码

CPP

#include<bits/stdc++.h>
#define F(i,a,b) for(int i(a),i##i##end(b);i<=i##i##end;++i)
#define R(i,a,b) for(int i(a),i##i##end(b);i>=i##i##end;--i)
#define ll long long
#define File(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
using namespace std;
const int MAXN=5001,MOD=1e9+7;
inline ll qpow(ll b,int e){ll res=1;while(e)(e&1)&&(res=res*b%MOD),b=b*b%MOD,e>>=1;return res;}
int n,m,a[MAXN];
int vis[MAXN],phi[MAXN];
vector<int>pr;
inline void init(){
	phi[1]=1;
	F(i,2,m){
		if(!vis[i]) vis[i]=i,phi[i]=i-1,pr.emplace_back(i);
		for(int j:pr){
			int k=i*j;
			if(k>m) break;
			vis[k]=j;
			if(vis[i]==j){phi[k]=phi[i]*j;break;}
			else phi[k]=phi[i]*(j-1);
		}
	}
}
int D[MAXN],G[MAXN][MAXN];
inline ll det(){
	bool inv=0;
	ll res=1;
	F(i,1,m){
		int t=-1;
		F(j,i,m) if(G[j][i]){t=j;break;}
		if(t==-1) return 0;
		if(t!=i) swap(G[t],G[i]),inv^=1;
		res=res*G[i][i]%MOD;
		vector<int>pos;
		F(j,i,m) if(G[i][j]) pos.emplace_back(j);
		ll inv=qpow(MOD-G[i][i],MOD-2)%MOD;
		F(j,i+1,m) if(G[j][i]){
			ll coef=G[j][i]*inv%MOD;
			for(int k:pos) G[j][k]=(G[j][k]+G[i][k]*coef)%MOD;
		}
	}
	return inv?MOD-res:res;
}
signed main(){ 
	ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
	cin>>n;
	F(i,1,n) cin>>a[i],m=max(m,a[i]);
	init();
	F(i,1,n) F(j,1,n) D[i]+=__gcd(a[i],a[j]);
	ll coef=1;
	F(i,1,n-1) coef=coef*D[i]%MOD,D[i]=qpow(D[i],MOD-2);
	F(i,1,m) F(j,1,m) if(i*j/__gcd(i,j)<=m){
		ll qwq=0;
		F(k,1,n-1) if(a[k]%i==0&&a[k]%j==0) (qwq+=D[k])>=MOD&&(qwq-=MOD);
		(G[m-i+1][m-j+1]=((i==j)-phi[j]*qwq)%MOD)<0&&(G[m-i+1][m-j+1]+=MOD);
	}
	cout<<coef*det()%MOD;
	return 0;
}

Day 92

生成子群相关完全不会啊。

2025/02/03 [PA 2024] Grupa permutacji

题意

给定

k

个长为

n

的置换，求它们生成子群的逆序对的平均数对

10^9+7

取模的值。

思路

生成子群最重要的性质是，假设这个生成子群的所有置换中的第

i

位有

k

种取值，那么每种取值的置换个数相同。

这个性质的推论是，选出若干位组成一个向量，这个向量的每种取值对应的置换个数也是相等的。

在本题中，我们可以考虑对所有

i\neq j

的二元组

(i,j)

建点，

(i,j)

和所有

(p_i,p_j)

连双向边，则一个连通块中的所有元素就是这两位可能的值。维护连通块中

i<j

和

i>j

的点数，设分别为

a,b

，则贡献为

\dfrac{ab}{a+b}

。

直接维护是

O(n^2k)

的，跑不过去。

前面的

O(n^2)

基本上没法再优化了。我们试图优化一下

O(k)

。

有一个确定性做法是 Schreier–Sims 算法，但是我不会。你感觉一下，我们随机选出

O(\log n)

个给出置换的子集复合起来，得到的所有置换大概率覆盖了所有上面图的边。

所以复杂度变成了

O(n(n+k)\log n)

。

代码

CPP

#include<bits/stdc++.h>
#define File(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
#define ll long long
#define F(i,a,b) for(int i(a),i##i##end(b);i<=i##i##end;++i)
#define R(i,a,b) for(int i(a),i##i##end(b);i>=i##i##end;--i)
using namespace std;
const int MAXN=3001,MOD=1e9+7;
int n,k,a[MAXN][MAXN],dsu[MAXN*MAXN];
inline int id(int i,int j){
	return (i-1)*n+j;
}
int find(int x){
	return x==dsu[x]?x:dsu[x]=find(dsu[x]);
}
mt19937 gen(time(0)^*new int);
ll le[MAXN*MAXN],ge[MAXN*MAXN];
inline ll qpow(ll base,int expo=MOD-2){
	ll res=1;
	while(expo){
		(expo&1)&&(res=res*base%MOD);
		base=base*base%MOD,expo>>=1;
	}
	return res;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>k;
	F(i,1,k) F(j,1,n) cin>>a[i][j];
	iota(dsu+1,dsu+n*n+1,1);
	F(T,1,40){
		static int p[MAXN],pp[MAXN];
		iota(p+1,p+n+1,1);
		F(i,1,k) if(gen()&1){
			F(j,1,n) pp[p[j]]=a[i][j];
			swap(p,pp);
		}
		F(i,1,n) F(j,1,n) if(i!=j) dsu[find(id(p[i],p[j]))]=find(id(i,j));
	}
	F(i,1,n) F(j,1,n) if(i!=j){
		if(i<j) ++le[find(id(i,j))];
		else ++ge[find(id(i,j))];
	}
	int ans=0;
	F(i,1,n) F(j,1,n) if(i!=j&&find(id(i,j))==id(i,j)) ans=(ans+le[id(i,j)]*ge[id(i,j)]%MOD*qpow(le[id(i,j)]+ge[id(i,j)]))%MOD;
	cout<<ans;
	return 0;
}

Day 93

太久没写了，随便找了一道，结果是金牌题……

和数学过情人节。

2025/02/14 [AGC063F] Simultaneous Floor

题意

求把

(a_1,a_2)

变成

(b_1,b_2)

的最小操作次数，一次操作定义为选择一个正实数

x

，执行

(a_1,a_2)\leftarrow (\lfloor a_1x\rfloor,\lfloor a_2x\rfloor)

，或报告无解。

思路

把有序数对看成坐标，扔到平面直角坐标系上研究。下面记点

A(a_1,a_2),B(b_1,b_2)

。不加说明时，我们均指第一象限。记值域为

V

。

发现点

P(x,y)

可以变成形如

(i,\lfloor\dfrac{y}{x}i\rfloor),(\lfloor\dfrac {x}{y}i\rfloor,i),i\in\mathbb Z

的点。不过还是有向下取整，不好描述。

那么倒过来看，对于

Q(p,q)

，能够到达它的

P

的集合是什么。

设直线

OP:y=kx

，如果

P

能到达

Q

，则

OP

必须穿过以

Q

为左下角、边长为

1

的正方形，穿过是指

OP

在正方形内的部分的长度

>0

。

设

Q_u(p,q+1),Q_r(p+1,q)

，则只要

OP

在

\angle Q_rOQ_u

内部（不包括

OQ_u,OQ_r

），其就会穿过这个正方形。

那么就有

k\in(k_{OQ_r},k_{OQ_u})

，即能够到达

Q(p,q)

的

P\in\{(x,y)|\dfrac{q}{p+1}<\dfrac y x<\dfrac{q+1}p\}

。

设

l_1=\dfrac{b_2}{b_1+1},r_1=\dfrac{b_2+1}{b_1}

，我们就可以算出经过

\le 1

次操作到达

B

的点的集合为

S_1=\{(x,y)|l_1<\dfrac y x<r_1\}

。

同理，设

l_2=\min\{\dfrac y{x+1}|(x,y)\in S_1\},r_2=\max\{\dfrac{y+1}x|(x,y)\in S_1\}

，则经过

\le 2

次操作到达

B

的点的集合为

S_2=\{(x,y)|l_2<\dfrac y x<r_2\}

。

更一般地，对于

t\ge 2

，设

l_t=\min\{\dfrac y{x+1}|(x,y)\in S_{t-1}\},r_t=\max\{\dfrac{y+1}x|(x,y)\in S_{t-1}\}

，则经过

\le t

次操作到达

B

的点的集合为

S_t=\{(x,y)|l_t<\dfrac y x<r_t\}

。

先来研究已知

l_{t-1},r_{t-1}

如何求

l_t,r_t

。下面只讨论

l_t

，

r_t

是类似的。

问题相当于求最小的

\dfrac{y}{x+1}

，满足

l_{t-1}<\dfrac{y}{x}<r_{t-1}

。考虑到

\dfrac{y}{x+1}=\dfrac{1}{\frac{x}{y}+\frac{1}{y}}

，即我们要

y

尽量小

\dfrac{x}{y}

尽量大。在

y

最小的同时取

x

最大即可，可以用反证法和一些缩放证明。

同理，求

r_t

时找满足

x

最小的最大

y

即可。

找到这样的

x,y

可以在 SBT 上二分实现。

接下来就是要求第一次满足

A\in S_t

的

t

。打表发现

l_t,r_t

在迭代若干轮之后就不变了，所以可以暴力求每一轮的

l_t,r_t

是多少。考虑到

l,r

在 SBT 上移动的过程，得到

x=1

或

y=1

后就不会变了，所以迭代次数是

O(\log V)

的。

注意有点在坐标轴、

y=x

上以及不在

y=x

同一侧的时候判无解。可以用关于

y=x

对称简化讨论。

总的复杂度是

O(T\log^2 V)

。

代码

CPP

#include<bits/stdc++.h>
#define File(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
#define ll long long
#define F(i,a,b) for(int i(a),i##i##end(b);i<=i##i##end;++i)
#define R(i,a,b) for(int i(a),i##i##end(b);i>=i##i##end;--i)
using namespace std;
struct Frac{
	ll x,y;
	Frac(const ll&a=0,const ll&b=0):x(a),y(b){}
	inline void reduce(){ll qwq=__gcd(x,y);x/=qwq,y/=qwq;}
	inline Frac inv(){return Frac(y,x);}
	bool operator<(const Frac&qwq)const{return x*qwq.y<y*qwq.x;}
	bool operator==(const Frac&qwq)const{return x==qwq.x&&y==qwq.y;}
};
Frac find(Frac ql,Frac qr){
	Frac l=Frac(0,1),r=Frac(1,0),now=Frac(1,1);
	while(!(ql<now&&now<qr)){
		if(!(ql<now)){
			ll fac=(ql.x*now.y-ql.y*now.x)/(ql.y*r.x-ql.x*r.y)+1;
			now=Frac(now.x+fac*r.x,now.y+fac*r.y),l=Frac(now.x-r.x,now.y-r.y);
		}else{
			ll fac=(qr.y*now.x-qr.x*now.y)/(qr.x*l.y-qr.y*l.x)+1;
			now=Frac(now.x+fac*l.x,now.y+fac*l.y),r=Frac(now.x-l.x,now.y-l.y);
		}
	}
	if(now.y==1) now.x=(qr.x-1)/qr.y;
    now.reduce();
    return now;
}
ll a1,a2,b1,b2;
inline int solve(){
	if(a1>a2) swap(a1,a2),swap(b1,b2);
	Frac a=Frac(a1,a2),b=Frac(b1,b2);
	if(a==b) return 0;
	if(!a1&&!a2) return -1;
	if(!a1) return b1?-1:1;
	if(!b1&&!b2) return 1;
	if(a1==a2) return b1==b2?1:-1;
	if(b1>b2) return -1;
	if(!b1) return 1+(a2<=a1*b2);
	Frac l(b1,b2+1),r(b1+1,b2);
	l.reduce(),r.reduce(),a.reduce();
	if(Frac(1,b2/b1+1)<a){
		int t=1;
		while(!(l<a&&a<r)){
			++t;
			Frac nl=l.x>1?find(r.inv(),l.inv()).inv():Frac(l.x,l.y-1),nr=r.y>1?find(l,r):Frac(r.x-1,r.y);
			l=nl,r=nr;
			++l.y,++r.x;
			l.reduce(),r.reduce();
		}
		return t;
	}
	return -1;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int T;
	for(cin>>T;T;--T){
		cin>>a1>>a2>>b1>>b2;
		cout<<solve()<<"\n";
	}
	return 0;
}

Day 94

看过的没写代码的题，回旋镖正中靶心。

2025/02/19 『JROI-4』少女幻葬

题意

给定

n,k

，求有多少个长为

n

的序列

a_1,\cdots,a_n

，满足

l_i\le a_i\le r_i,\gcd(a_i,a_{i+1})\neq k,\gcd(a_i,a_{i+1},a_{i+2})=k

。

思路

记值域为

m

。

由于

\gcd(a_i,a_{i+1},a_{i+2})=k

，所以有

k|a_i

。不妨令

a_i\leftarrow\dfrac{a_i}{k},l_i\leftarrow\lceil\dfrac{l_i}{k}\rceil,r_i\leftarrow\lfloor\dfrac{r_i}{k}\rfloor

。则原限制转化为

l_i\le a_i\le r_i,\gcd(a_i,a_{i+1})\neq 1,\gcd(a_i,a_{i+1},a_{i+2})=1

。接下来的

k

和题目里的没有关系。

设一个状态转移会比较抽象。设

f(i,j,k)

表示考虑到第

i

个数，

a_i=k

，

\gcd(a_i,a_{i-1})=j

的方案数；设

g(i,j,k)

表示考虑到第

i

个数，

a_i=k

，

\gcd(a_i,a_{i+1})=j

的方案数。

首先是

g

到

f

的转移为

f(i,j,k)=\sum\limits_{v=l_{i-1}}^{r_{i-1}}g(i-1,j,v)[\gcd(v,k)=j]

。

除掉

j

后反演得到

f(i,j,k)=\sum\limits_{v=\lceil\frac{l_{i-1}}{j}\rceil}^{\lfloor\frac{r_{i-1}}{j}\rfloor}g(i-1,j,vj)\sum\limits_{d|v,d|\frac{k}{j}}\mu(d)

。

即：

f(i,j,k)=\sum\limits_{d|\frac{k}{j}}\mu(d)\sum\limits_{v=\lceil\frac{l_{i-1}}{dj}\rceil}^{\lfloor\frac{r_{i-1}}{dj}\rfloor}g(i-1,j,vdj)

不妨

k\leftarrow \dfrac k j

，对第三维做狄利克雷后缀和，对位乘

\mu

后再做狄利克雷前缀和即可转移，时间复杂度

O(nm\log m\log\log m)

，前一个

\log m

是枚举因数的调和级数，后一个

\log\log m

是狄利克雷前后缀和。

然后再是

f

到

g

的转移为：

g(i,j,k)=\sum\limits_{x|k}f(i,x,k)[\gcd(x,j)=1]

枚举

k

，把

f(i,x,k)

贡献到

x

的质因数集合的位置然后求高维后缀和，那么

g(i,j,k)

就是

j

的质因数集合的补集的位置。这一部分复杂度是

\sum\limits_{k\le m}d(k)\omega(k)=\sum\limits_{k\le m}\omega(k)\sum\limits_{i|k}1=\sum\limits_{ik\le m}\omega(ik)\le\sum\limits_{ik\le m}(\omega(i)+\omega(k))=2\sum\limits_{i\le m}\sum\limits_{k\le\frac m i}\omega(i)=2\sum\limits_{i\le m}O(\dfrac m i\log\log\dfrac v i)=O(m\log m\log\log m)

。加上枚举第一维，总的复杂度是

O(nm\log m\log\log m)

。

然后就做完了，时间复杂度

O(nm\log m\log\log m)

。

代码

CPP

#include<bits/stdc++.h>
#define File(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
#define ll long long
#define F(i,a,b) for(int i(a),i##i##end(b);i<=i##i##end;++i)
#define R(i,a,b) for(int i(a),i##i##end(b);i>=i##i##end;--i)
using namespace std;
const int MAXN=2001,MAXV=5001,MOD=998244353;
inline void add(int&x,int y){(x+=y)>=MOD&&(x-=MOD);}
int n,m,l[MAXN],r[MAXN],tot;
int pr[MAXV],cnt,vis[MAXV],mu[MAXV],omega[MAXV];
inline void init(){
	mu[1]=1;
	F(i,2,m){
		!vis[i]&&(pr[++cnt]=i,vis[i]=i,mu[i]=-1);
		F(j,1,cnt){
			int t=i*pr[j];
			if(t>m) break;
			vis[t]=pr[j];
			if(vis[i]==pr[j]) break;
			else mu[t]=-mu[i];
		}
	}
	return;
}
vector<int>fac[MAXV];
int id[MAXV][MAXV];
int f[50000],g[50000],tmp[50000],pf[50000];
int sum[130];
signed main(){ 
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int k=0;
	cin>>n>>k;
	F(i,1,n) cin>>l[i]>>r[i],l[i]=(l[i]-1)/k+1,r[i]=r[i]/k,m=max(m,r[i]);
	init();
	F(i,1,m) for(int j=i;j<=m;j+=i) fac[j].push_back(i),id[j][i]=++tot;
	F(i,2,m){
		static int idx[MAXV];
		int now=0,qwq=i,qaq=-1;
		while(qwq!=1){
			if(now!=vis[qwq]) now=vis[qwq],idx[now]=++qaq;
			qwq/=vis[qwq];
		}
		omega[i]=qaq+1;
		for(int j:fac[i]){
			qwq=j;
			while(qwq!=1) pf[id[i][j]]|=(1<<idx[vis[qwq]]),qwq/=vis[qwq];
		}
	}
	F(i,2,m) for(int j=((l[1]-1)/i+1)*i;j<=r[1];j+=i) g[id[j][i]]=1;
	F(i,2,n){
		F(j,2,m){
			for(int k=j,qwq=1;k<=m;k+=j,++qwq) tmp[qwq]=g[id[k][j]];
			int lim=m/j;
			F(k,1,cnt){
				if(pr[k]>lim) break;
				for(int t=lim/pr[k]*pr[k];t>=pr[k];t-=pr[k]) add(tmp[t/pr[k]],tmp[t]);
			}
			F(k,1,lim) (tmp[k]=tmp[k]*mu[k])<0&&(tmp[k]+=MOD);
			F(k,1,cnt){
				if(pr[k]>lim) break;
				for(int t=pr[k];t<=lim;t+=pr[k]) add(tmp[t],tmp[t/pr[k]]);
			}
			for(int k=j,qwq=1;k<=m;k+=j,++qwq) f[id[k][j]]=tmp[qwq];
		}
		F(j,2,m) for(int k=j;k<=m;k+=j) if(k<l[i]||k>r[i]) f[id[k][j]]=0;
		F(k,2,m){
			F(j,0,(1<<omega[k])-1) sum[j]=0;
			for(int j:fac[k]) if(j!=1) add(sum[pf[id[k][j]]],f[id[k][j]]);
			F(j,0,omega[k]-1) F(s,0,(1<<omega[k])-1) if(s>>j&1) add(sum[s],sum[s^(1<<j)]);
			for(int j:fac[k]) if(j!=1) g[id[k][j]]=sum[((1<<omega[k])-1)^pf[id[k][j]]];
		}
	}
	int ans=0;
	F(i,2,m) for(int j=i;j<=m;j+=i) add(ans,f[id[j][i]]);
	cout<<ans;
	return 0;
}

Day 95

一个很厉害的技巧。

2025/02/22 [ABC311Ex] Many Illumination Plans

题意

有一个以

1

为根的有

n

个节点的树，每一个点有权值值

B_i

、重量

W_i

和颜色

C_i\in\{0,1\}

。要求对于每一个点

u

的子树

T_u

回答以下问题：

可以对

T_u

进行若干次操作，每一次选择一个非根节点，将这个点的所有儿子转移给其父亲，然后删去该节点。操作后应满足

T_u

中不存在两端点同色的边，所有点的重量和小于

X

。问操作之后的

T_u

的权值之和的最大值。

思路

先讨论求以

1

为根子树的答案。

删除顺序是不重要的，所以可以当成选几个点满足重量和

\le X

、与选中的点里最近的祖先颜色不同，使得权值和最大。也就是背包。

于是设

dp(i,j,k)

表示当前在节点

i

子树中、重量和为

j

、最浅的点的颜色为

k

的最大权值和，转移为对于

u

的儿子

v

把

dp(u,*,C_u)

为

dp(u,*,C_u)

和

dp(v,*,1-C_u)

的

\max

卷积。

然后你发现完蛋了，

\max

卷积是

O(X^2)

的。但是一个插入数是

O(X)

的，我们只要想办法把

\max

卷积变成插入一个数就好了。

怎么办呢？你发现

\max

卷积具有交换律和结合律，所以我们可以随便改变运算顺序。再加上每次我们初始的时候

dp

数组都为空，这个很浪费。不如每次递归子树时传入现在的“半成品”

dp

数组，回溯的时候把当前节点的贡献再加进去。由于

k

有两种取值，我们要 dfs 两次子树，每个点被访问了

O(\text{祖先个数次})

，总的复杂度变成了

O(n^2X)

。已经比

O(nX^2)

好了！

在下一步我们使用多次递归子树的经典 Trick：轻重子树分治。你考虑第一次递归进去的时候

dp(u,*,0),dp(u,*,1)

都是

\max

卷积的幺元，这两个没有区分，只需要递归一次。所以先递归一次重儿子，轻儿子再递归两次。

分析一下复杂度。设

n

个点的树复杂度为

T(n)

，重儿子子树大小为

h

，其他子树大小为

y_1,\cdots,y_t

，则

T(n)=T(h)+O(C)+2\sum\limits_{i=1}^t T(y_i)

。显然复杂度高于

O(n)

，此时根据调整法取

y_1=n-1-h,y_2=\cdots=y_t=0

取到最大

T(h)+2T(n-1-h)

。进一步，由于

n-1-h\le h

，取

h=\dfrac{n-1}{2}

最优，即

T(n)\le 3T(\dfrac n 2)+O(C)

。根据主定理，得到复杂度上界

O(n^{\log_2 3}C)

。

然后是对每个子树求。你发现上面这个东西一次求了一条重链的答案，所以再遍历一遍轻子树即可，复杂度仍然是

O(n^{\log_2 3}C)

，其中

\log_2 3\approx 1.582

。

代码

CPP

#include<bits/stdc++.h>
#define File(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
#define ll long long
#define F(i,a,b) for(int i(a),i##i##end(b);i<=i##i##end;++i)
#define R(i,a,b) for(int i(a),i##i##end(b);i>=i##i##end;--i)
#define poly vector<ll>
#define fi first
#define se second
using namespace std;
const int MAXN=201,MAXV=50001;
int n,X,W[MAXN],C[MAXN],fa[MAXN],siz[MAXN],son[MAXN];
ll ans[MAXN],B[MAXN];
vector<int>g[MAXN];
void dfs1(int now){
	siz[now]=1;
	for(int i:g[now]) dfs1(i),siz[now]+=siz[i],siz[son[now]]<siz[i]&&(son[now]=i);
	return;
}
poly zero;
vector<poly> dfs2(int now,poly dp,bool heavy){
	if(!heavy) for(int i:g[now]) if(i!=son[now]) dfs2(i,dp,0);
	vector<poly>qwq(2,zero);
	if(son[now]){
		qwq=dfs2(son[now],dp,heavy);
		for(int i:g[now]) if(i!=son[now]) F(j,0,1) qwq[j]=dfs2(i,qwq[j],1)[j];
	}else qwq[0]=qwq[1]=dp;
	R(i,X,W[now]){
		qwq[C[now]][i]=max(qwq[C[now]][i],qwq[C[now]^1][i-W[now]]+B[now]);
		if(!heavy) ans[now]=max(ans[now],qwq[C[now]^1][i-W[now]]+B[now]);
	}
	return qwq;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>X;
	F(i,2,n) cin>>fa[i],g[fa[i]].push_back(i);
	F(i,1,n) cin>>B[i]>>W[i]>>C[i];
	dfs1(1);
	zero=poly(X+1,-5e17);
	zero[0]=0;
	dfs2(1,zero,0);
	F(i,1,n) cout<<ans[i]<<"\n";
	return 0;
}

Day 96

五合一。

2025/02/24 [CEOI 2020] 象棋世界

题意

在

r

行

c

列的棋盘上，

q

组询问兵、车、后、象、王从

(1,c_1)

到

(r,c_r)

的最小步数和达到最小步数的方案数，或判断到达不了。保证

r\ge c

。

思路

兵

c_1\neq c_r

时到不了，否则最小步数为

r

，方案数为

1

。

车

c_1\neq c_r

时最小步数为

2

，方案数为

2

；否则最小步数为

1

，方案数为

1

。

后

先特判一步可以到的情况，这种情况都只有

1

种方案。

剩下的情况不超过两步，枚举每一种情况即可。

以上都是

O(1)

的。

象

先判如果坐标之和奇偶性不同就无解。

否则必然是像踢墙跳一样来回走直到走到

(x,c_r)

满足

x\ge r

，最优步数

y

就求出来了。

方案数的话，就是在每次转弯的地方少走几步，用隔板法可以算出来是

\dbinom{y-1+\frac{x-r}{2}-1}{\frac{x-r}{2}}

。

由于

y\le c

，复杂度

O(c)

。

王

显然走

r-1

步。下面设

c_1=a,c_r=b

，我们要求从

(1,a)

到

(r,b)

的方案数，每步可以从

(x,y)

走到

(x+1,y+1),(x+1,y),(x+1,y-1)

，且不能碰

(x,0),(x,c+1)

这两条线。

这是一个经典问题。设

f_i

表示不考虑不能碰到的方案数，使用反射容斥，得到答案为

\sum\limits_{k\equiv b-a\pmod{2c+2}}f_k-\sum\limits_{k\equiv -a-b\pmod{2c+2}}f_k

。

注意到

f_k=[x^k](x+1+x^{-1})^{r-1}

，做循环卷积即可。预处理复杂度

O(c^2\log r)

或

O(c\log c\log r)

，询问复杂度

O(1)

。

代码

CPP

#include<bits/stdc++.h>
#define File(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
#define ll long long
#define F(i,a,b) for(int i(a),i##i##end(b);i<=i##i##end;++i)
#define R(i,a,b) for(int i(a),i##i##end(b);i>=i##i##end;--i)
using namespace std;
const int MAXN=4010,MOD=1e9+7;
int r,c,q,len;
ll fact[MAXN],inv[MAXN];
inline ll C(ll x,ll y){
	ll res=inv[y];
	F(i,0,y-1) res=res*(x-i)%MOD;
	return res;
}
struct Poly{
	ll v[MAXN]={};
	Poly operator*(const Poly&x)const{
		Poly res;
		F(i,0,len-1) F(j,0,len-1) res.v[(i+j)%(2*c+2)]=(res.v[(i+j)%(2*c+2)]+v[i]*x.v[j])%MOD;
		return res;
	}
}base,f;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>r>>c>>q;
	len=2*c+2,fact[0]=fact[1]=inv[0]=inv[1]=1;
	F(i,2,len) fact[i]=fact[i-1]*i%MOD,inv[i]=MOD-MOD/i*inv[MOD%i]%MOD;
	F(i,2,len) inv[i]=inv[i-1]*inv[i]%MOD;
	base.v[0]=base.v[1]=base.v[2*c+1]=1;
	f.v[0]=1;
	int expo=r-1;
	while(expo){
		(expo&1)&&(f=f*base,1);
		base=base*base,expo>>=1;
	}
	for(;q;--q){
		char T;
		int a,b;
		cin>>T>>a>>b;
		switch(T){
			case 'P':{
				if(a!=b) cout<<"0 0\n";
				else cout<<r-1<<" 1\n";
				break;
			}case 'R':{
				if(a!=b) cout<<"2 2\n";
				else cout<<"1 1\n";
				break;
			}case 'Q':{
				if(a==b||abs(b-a)==r-1){
					cout<<"1 1\n";
					continue;
				}
				int ans=4;
				if(r==c){
					if(a==1||a==c) ++ans;
					if(b==1||b==c) ++ans;
				}
				if(((1+a)&1)==((r+b)&1)){
					if(a+b+r-1<=2*c) ++ans;
					if(a+b-r+1>=2) ++ans;
				}
				cout<<"2 "<<ans<<"\n";
				break;
			}case 'B':{
				if(((1+a)&1)!=((r+b)&1)){
					cout<<"0 0\n";
					break;
				}
				int step=0x7fffffff,pos,x,ans=0;
				F(O,0,1){
					if(O) pos=a,x=1;
					else pos=c-a+1,x=c;
					int qaq=(r-pos)/(2*c-2),now=qaq*2;
					pos+=(2*c-2)*qaq;
					while(pos<r||x!=b){
						++now;
						if(x==1){
							if(pos+b-1>=r){
								pos+=b-1;
								break;
							}
							pos+=c-1,x=c;
						}else if(x==c){
							if(pos+c-b>=r){
								pos+=c-b;
								break;
							}
							pos+=c-1,x=1;
							continue;
						}
					}
					if(step>now) step=now,ans=0;
					if(step==now){
						int d=(pos-r)/2;
						(ans+=C(d+now-1,d))>=MOD&&(ans-=MOD);
					}
				}
				cout<<step+1<<" "<<ans<<"\n";
				break;
			}case 'K':{
				cout<<r-1<<" "<<(f.v[(b-a+len)%len]-f.v[(-b-a+len)%len]+MOD)%MOD<<"\n";
				break;
			}
		} 
	}
	return 0;
}

Day 97

在省队名单出之前，赶快写几篇吧。

2025/03/04 [ARC070F] HonestOrUnkind

题意

有

a

个好人和

b

个坏人。你可以向

i

询问

j

是不是好人。好人永远说真话，坏人会用某种策略回答。用不超过

2(a+b)

次询问出每个人是好人还是坏人，或判断不可能问出来。

思路

首先如果

a\le b

，那么坏人中挑

a

个出来互相指认是好人并说其他人都是坏人，这样永远无法区分好坏。

否则

a>b

。考虑维护一个栈，满足栈里存在一个分界点，往栈顶都是好人，往栈底都是坏人。从小到达枚举

i

，如果栈空直接入栈，否则向栈顶询问

i

是不是好人。

如果栈顶回答是好人，那么无论如何把

i

入栈都不会破坏栈的性质，直接入栈。

否则，我们不仅不让

i

入栈，还把栈顶弹掉。这样要么是两个坏人消掉了，要么是一个好人一个坏人消掉了，仍然满足好人更多。这里询问次数

<a+b

。

既然好人始终更多，最后的栈顶就是好人。挨个问一遍这个好人即可。这里询问次数

a+b-1

，满足条件。

时间复杂度

O(a+b)

。

代码

CPP

#include<bits/stdc++.h>
#define F(i,a,b) for(int i(a),i##i##end(b);i<=i##i##end;++i)
#define R(i,a,b) for(int i(a),i##i##end(b);i>=i##i##end;--i)
#define ll long long
#define File(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
using namespace std;
const int MAXN=2e5+2;
int a,b;
inline char ask(int x,int y){
	cout<<"? "<<x<<" "<<y<<endl;
	char ch;
	cin>>ch;
	return ch;
}
int stk[MAXN],tp;
char ans[MAXN];
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>a>>b;
	if(a<=b) return cout<<"Impossible",0;
	F(i,0,a+b-1){
		if(!tp){
			stk[++tp]=i;
			continue;
		}
		if(ask(stk[tp],i)=='Y') stk[++tp]=i;
		else --tp;
	}
	F(i,0,a+b-1) ans[i]=int(ask(stk[tp],i)=='Y')+'0';
	cout<<"! "<<ans;
	return 0;
}

Day 98

是少见的条件概率题。

2025/03/07 [CTSC2017] 游戏

题意

小 R 和小 B 玩了 n 局游戏。第

1

局游戏小 R 获胜的概率是

p_1

，小 B 获胜的概率是

1 −p_1

。如果第

i − 1

局游戏小 R 获胜，那么第

i

局游戏小 R 获胜的概率为

p_i

，小 B 获胜的概率为

1 − p_i

；如果第

i − 1

局游戏小 B 获胜，那么第

i

局游戏小 R 获胜的概率为

q_i

，小 B 获胜的概率为

1 − q_i

。

你现在有若干条信息，每条形如某一局谁赢了。你需要支持加入信息，删除信息，求以当前所有信息为前提时小 R 的期望获胜局数。

思路

根据期望的线性性，把每一局小 R 赢的条件概率加起来就是所求的条件期望。

然后发现影响第

i

局的信息只有左右两边第一个已知结果的位置

l,r

。设事件

L,R

分别表示第

l,r

局给定的获胜情况，事件

X

为第

i

局小 R 获胜。所求即为

P(X|LR)

。

使用条件概率的定义得到

P(X|LR)=\dfrac{P(LRX)}{P(LR)}=\dfrac{P(L)P(X|L)P(R|X)}{P(L)P(R|L)}=\dfrac{P(X|L)P(R|X)}{P(R|L)}

。

首先是分母。维护一个二维行向量

[b,r]

分别表示小 R 输和赢的概率，每次转移就是右乘上矩阵

\begin{bmatrix}1-q_i & q_i\\1-p_i & p_i\end{bmatrix}

。发现分母的条件概率相当于是钦定第

l

局的行向量是

[1,0]

或

[0,1]

，直接维护矩阵区间积即可。

然后是分子。比起分母，分子相当于是把某一局强行钦定为小 R 赢，即把转移矩阵的第一列都改为

0

。使用矩阵乘法的分配律即可维护。

找

l,r

可以用 set 维护，修改时减去老区间的贡献加上新区间的贡献。为了方便，可以加上第

0

局和第

n+1

局并让小 R 在这两局胜。

时间复杂度

O(n\log n)

。

代码

CPP

#include<bits/stdc++.h>
#define F(i,a,b) for(int i(a),i##i##end(b);i<=i##i##end;++i)
#define R(i,a,b) for(int i(a),i##i##end(b);i>=i##i##end;--i)
#define ll long long
#define File(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
using namespace std;
const int MAXN=2e5+2;
int n,m;
double p[MAXN],q[MAXN];
struct Mat{
	double v[2][2];
	Mat(const double&a=0,const double&b=0,const double&c=0,const double&d=0){v[0][0]=a,v[0][1]=b,v[1][0]=c,v[1][1]=d;}
	Mat operator+(const Mat&x)const{return Mat(v[0][0]+x.v[0][0],v[0][1]+x.v[0][1],v[1][0]+x.v[1][0],v[1][1]+x.v[1][1]);}
	Mat operator*(const Mat&x)const{return Mat(v[0][0]*x.v[0][0]+v[0][1]*x.v[1][0],v[0][0]*x.v[0][1]+v[0][1]*x.v[1][1],v[1][0]*x.v[0][0]+v[1][1]*x.v[1][0],v[1][0]*x.v[0][1]+v[1][1]*x.v[1][1]);}
}; 
struct Node{
	Mat ch,mo;
	Node operator*(const Node&x)const{return (Node){ch*x.mo+mo*x.ch,mo*x.mo};}
}segt[MAXN<<2];
#define lc (now<<1)
#define rc (now<<1|1)
#define mid ((l+r)>>1)
#define ls lc,l,mid
#define rs rc,mid+1,r
void build(int now,int l,int r){
	if(l==r){
		segt[now].mo=Mat(1-q[l],q[l],1-p[l],p[l]);
		segt[now].ch=Mat(0,0,1-p[l],p[l]);
		return;
	}
	build(ls),build(rs);
	segt[now]=segt[lc]*segt[rc];
	return;
}
Node qry(int now,int l,int r,int ql,int qr){
	if(ql<=l&&r<=qr) return segt[now];
	if(qr<=mid) return qry(ls,ql,qr);
	else if(ql>mid) return qry(rs,ql,qr);
	else return qry(ls,ql,qr)*qry(rs,ql,qr);
}
set<int>info;
bool win[MAXN];
double ask(int l,int r){
	Node qwq=qry(1,1,n+1,l+1,r);
	return qwq.ch.v[win[l]][win[r]]/qwq.mo.v[win[l]][win[r]];
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cout<<fixed<<setprecision(6);
	char type;
	cin>>n>>m>>type;
	cin>>p[1];
	F(i,2,n) cin>>p[i]>>q[i];
	win[0]=win[n+1]=1;
	p[n+1]=q[n+1]=1;
	build(1,1,n+1);
	info.insert(0),info.insert(n+1);
	double ans=ask(0,n+1);
	for(;m;--m){
		char op[4];
		int pos;
		cin>>op>>pos;
		if(op[0]=='a'){
			cin>>win[pos];
			auto it=info.lower_bound(pos);
			int l=*prev(it),r=*it;
			info.insert(pos);
			ans-=ask(l,r),ans+=ask(l,pos),ans+=ask(pos,r);
		}else{
			info.erase(pos);
			auto it=info.lower_bound(pos);
			int l=*prev(it),r=*it;
			ans-=ask(l,pos),ans-=ask(pos,r),ans+=ask(l,r);
		}
		cout<<ans-1<<"\n";
	}
	return 0;
}

Day 99

完成立下的 flag。

2025/03/09 [湖北省选模拟 2025] 团队协作 / team

题意

对每个点求出包含这个点的所有独立集中点权最大值的和，对

998244353

取模。

思路

我们称节点

i

的点权比节点

j

大当且仅当

v_i>v_j

或

v_i=v_j,i>j

。

考虑转置原理：

【转置原理】 对于一个线性算法，我们可以通过倒序执行所有操作并把操作

x\leftarrow x+ky

改为

y\leftarrow y+kx

得到转置问题的算法，时间复杂度不变。

设

a_{i,j}

表示包含点

i

且点权最大的点为

j

的独立集个数，

n

阶方阵

A=(a_{i,j})

，列向量

\vec{a}=[v_1,v_2,\cdots,v_n]^{\top}

，则答案向量为

\vec b=A\vec a

。

它的转置问题即为：对于每个

i

，求满足

i

是独立集中点权最大的点的所有独立集的点权和。

按点权从小到大加入每个点，加入点

i

时所有独立集点权和的变化量就是

i

的答案。在这里，一个点被加入指的是可以在独立集中出现，未被加入指的是不能出现在独立集中。

这是一个经典的 ddp 问题，我们使用静态 top tree 解决。对每个簇设

f(0/1,0/1),g(0/1,0/1)

分别表示不选/选上界点、不选/选下界点的独立集方案数和权值和，转移是显然的。值得注意的是，此处

g(1,*)

我们不计入上界点的贡献。可以新建一个虚点

0

作为

1

的父亲方便统计答案。

如果把

f

视为常量（矩阵里的量），则转移关于

g

是线性的。

需要注意，你可以把 ddp 的每次修改看成持久化的，即我们修改的时候变量所占用的内存都是不同的，需要先赋值一次。

然后转置就行了。时间复杂度

O(n\log n)

。发现我们实际上并不需要持久化，每次直接覆盖就行，所以空间

O(n)

。如果还是不明白可以看代码，注释里标了转置前后的内容。

事实上，用转置原理得到的做法和其他几篇直接用 top tree 得到的做法是一样的。

代码

CPP

#include <bits/stdc++.h>
#define File(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
#define ll long long
#define F(i,a,b) for(int i(a),i##i##end(b);i<=i##i##end;++i)
#define R(i,a,b) for(int i(a),i##i##end(b);i>=i##i##end;--i)
#define fi first
#define se second
using namespace std;
const int MAXN=3e5+2,MOD=998244353;
int n;
pair<int,int>val[MAXN];
int cnt;
struct Node{
	short type;//-1unit,0rake,1compress
	int up,dn,mid;
	int siz,lc,rc,fa;
	ll f[2][2],g[2][2];
	Node(const int&t=-1,const int&d=0,const int&e=0,const int&a=1,const int&b=0,const int&c=0){
		type=t,siz=a,lc=b,rc=c,up=d,dn=e,fa=0;
		memset(f,0,sizeof(f)),memset(g,0,sizeof(g));
		return;
	}
}node[MAXN<<1];
bool isin[MAXN]; 
inline void upd(int now){
	Node&qwq(node[now]),&l(node[qwq.lc]),&r(node[qwq.rc]);
	memset(qwq.f,0,sizeof(qwq.f));
	if(node[now].type) F(i,0,1) F(j,0,1) F(k,0,isin[l.dn]) qwq.f[i][j]=(qwq.f[i][j]+l.f[i][k]*r.f[k][j])%MOD;
	else F(i,0,1) F(j,0,1) F(k,0,isin[r.dn]) qwq.f[i][j]=(qwq.f[i][j]+l.f[i][j]*r.f[i][k])%MOD;
	return;
}
inline void psd(int now){
	Node&qwq(node[now]),&l(node[qwq.lc]),&r(node[qwq.rc]);
	if(node[now].type){
		/*
		转置前 
		F(i,0,1) F(j,0,1) F(k,0,isin[l.dn]){
			qwq.g[i][j]=(qwq.g[i][j]+l.f[i][k]*r.g[k][j])%MOD;
			qwq.g[i][j]=(qwq.g[i][j]+l.g[i][k]*r.f[k][j])%MOD;
		}
		*/ 
		F(i,0,1) F(j,0,1) F(k,0,isin[l.dn]){
			r.g[k][j]=(r.g[k][j]+l.f[i][k]*qwq.g[i][j])%MOD;
			l.g[i][k]=(l.g[i][k]+r.f[k][j]*qwq.g[i][j])%MOD;
		}//倒不倒序不影响 
	}else{
		/*
		转置前 
		F(i,0,1) F(j,0,1) F(k,0,isin[r.dn]){
			qwq.g[i][j]=(qwq.g[i][j]+l.f[i][j]*r.g[i][k])%MOD;
			qwq.g[i][j]=(qwq.g[i][j]+l.g[i][j]*r.f[i][k])%MOD;
		}
		*/ 
		F(i,0,1) F(j,0,1) F(k,0,isin[r.dn]){
			r.g[i][k]=(r.g[i][k]+l.f[i][j]*qwq.g[i][j])%MOD;
			l.g[i][j]=(l.g[i][j]+r.f[i][k]*qwq.g[i][j])%MOD;
		}
	}
	memset(qwq.g,0,sizeof(qwq.g));
	return;
}
inline int merge(int x,int y,int type){
	node[x].fa=node[y].fa=++cnt;
	node[cnt]=Node(type,node[x].up,node[type?y:x].dn,node[x].siz+node[y].siz,x,y);
	return upd(cnt),cnt;
}
#define Poi vector<int>::iterator
int build(Poi l,Poi r,int type){
	if(l==r) return 0;
	if(l+1==r) return *l;
	int sum=0,all=0;
	for(auto it=l;it!=r;++it) all+=node[*it].siz;
	Poi mid=l+1;
	for(auto it=l;it!=r;++it){
		sum+=node[*it].siz;
		if(sum*2<=all) mid=it+1;
		else break;
	}
	return merge(build(l,mid,type),build(mid,r,type),type);
}
int siz[MAXN],fa[MAXN],son[MAXN],rt[MAXN];//根为 cnt 
vector<int>g[MAXN];
void dfs1(int now){
	siz[now]=1;
	node[now]=Node(-1,fa[now],now);
	node[now].f[0][0]=node[now].f[1][0]=node[now].f[0][1]=1;
	isin[now]=1;
	for(int i:g[now]){
		dfs1(i);
		siz[now]+=siz[i];
		if(siz[son[now]]<siz[i]) son[now]=i;
	}
	return;
}
void dfs2(int now,bool heavy){
	if(son[now]) dfs2(son[now],1);
	for(int i:g[now]) if(i!=son[now]) dfs2(i,0);
	if(!heavy){
		vector<int>chain;
		chain.push_back(now);
		for(int i(son[now]);i;i=son[i]){
			vector<int>sub({i});
			for(int j:g[fa[i]]) if(j!=i) sub.push_back(rt[j]);
			chain.push_back(build(sub.begin(),sub.end(),0));
		}
		rt[now]=build(chain.begin(),chain.end(),1);
	}
	return;
}
int ans[MAXN];
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	F(i,2,n) cin>>fa[i],g[fa[i]].push_back(i);
	F(i,1,n) cin>>val[i].fi,val[i].se=i;
	sort(val+1,val+n+1);
	dfs1(1),cnt=n,dfs2(1,0);
	R(i,n,1){//倒序执行 
		/*
		转置前 (ans[i]-ans[i-1])+=node[cnt].g[0][0/1] 
		转置后倒序变成 node[cnt].g[0][0/1]+=val[i]-val[i+1] 
		*/
		node[cnt].g[0][0]=(node[cnt].g[0][0]+val[i].fi-val[i+1].fi+MOD)%MOD;
		if(isin[node[cnt].dn]) node[cnt].g[0][1]=(node[cnt].g[0][1]+val[i].fi-val[i+1].fi+MOD)%MOD;
		int now=val[i].se,tp=0;
		static int path[MAXN];
		while(node[now].fa) path[++tp]=node[now].fa,now=path[tp];
		R(j,tp,1) psd(path[j]);//从上到下倒序执行 
		now=val[i].se;
		ans[now]=node[now].g[0][1],node[now].g[0][1]=0;//node[now].g[0][1]=val[now]的转置 
		isin[now]=0,node[now].f[0][1]=0; 
		while(node[now].fa) upd(node[now].fa),now=node[now].fa;//按原顺序更新常量（矩阵里的量） 
	}
	F(i,1,n) cout<<ans[i]<<" "; 
	return 0;
}

Day 100

现在不能公开。

后记

100 天蜜月日记完结撒花！

文章操作

前言

Day 91

题意

思路

代码

Day 92

题意

思路

代码

Day 93

题意

思路

代码

Day 94

题意

思路

代码

Day 95

题意

思路

代码

Day 96

题意

思路

兵

车

后

象

王

代码

Day 97

题意

思路

代码

Day 98

题意

思路

代码

Day 99

题意

思路

代码

Day 100

后记

相关推荐

评论