首页 > 其他分享 >abc351g 题解

abc351g 题解

时间:2024-04-28 15:11:58浏览次数:25  
标签:int 题解 ll son bmatrix mod now abc351g

这场 abc F、G 质量堪忧。怎么能扔板子上来呢?

板子:P4719 【模板】"动态 DP"&动态树分治

Solution

这种每次修改对后面询问有影响,又每次都要输出答案的,离线就基本做不了了,这时候就往动态算法想,其实做过几道 ddp 的题就看出来这是个板子。

由于题目中的式子性质优良,我们很明显可以把它写成矩阵的形式。

我们预处理轻儿子的乘积和,即 \(g_{u}=\prod\limits_{v\in son,v\ne Hson}f_v\) ,然后问题中的式子就可以写成这个矩阵:

\[\begin{bmatrix} f_{son} & 1 \\ \end{bmatrix} \times \begin{bmatrix} g_{now} & 0\\ a_{now} & 1\\ \end{bmatrix}= \begin{bmatrix} f_{now} & 1 \\ \end{bmatrix}\]

然后因为不方便转移,要从后往前乘,我们改造一下就变成:

\[\begin{bmatrix} g_{now} & a_{now}\\ 0 & 1\\ \end{bmatrix} \times \begin{bmatrix} f_{son} \\ 1 \end{bmatrix}= \begin{bmatrix} f_{now} \\ 1 \end{bmatrix} \]

初始矩阵是 \(\begin{bmatrix}0 \\ 1\end{bmatrix}\)。

这样就可以从根节点往下乘了。

然后之后操作修改就是模板了,撤销操作用逆元即可。

然后这题一个小麻烦的地方就来了。因为这题有 \(0\) ,然后 \(0\) 没有逆元,所以要进行一些适当的处理即可,这个地方我选择的使用一个数组记录下轻儿子 \(0\) 的个数,\(g\) 数组不乘 \(0\)。

然后就是 ddp 的一些细节了。

使用的是树剖的写法,\(w=2\) 是矩阵大小,还有个求逆元,时间复杂度 \(O(q\log^2 n\times w^3+q\log n\log mod)\) 。

因为笔者的习惯,代码中 \(f\) 代表上述的 \(g\) 数组,代码中的 \(g\) 数组代表矩阵。

Code

#include<bits/stdc++.h>
#define N 200005
#define ll long long
using namespace std;
const int mod=998244353;
ll inv(ll a,ll x=mod-2)
{
	ll res=1;
	while(x)
	{
		if(x&1) res=res*a%mod;
		a=a*a%mod;
		x>>=1;
	}
	return res;
}
int n;
int head[N],tot=1;
int a[N];
struct edge{
	int to,next;
}e[N*2];
void add(int u,int v)
{
	e[tot]=(edge){v,head[u]};
	head[u]=tot++;
}
ll f[N],w[N];
struct node{
	int r[2][2];
	int n,m;
}g[N],oo,zero;
node operator * (node a,node b)
{
	node c;
	c.n=a.n,c.m=b.m;
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++)
			c.r[i][j]=0;
	for(int k=0;k<2;k++)
		for(int i=0;i<2;i++)
			for(int j=0;j<2;j++)
				c.r[i][j]=(c.r[i][j]+(1ll*a.r[i][k]*b.r[k][j]%mod))%mod;
	return c;
}
int pos[N];
struct segtree{
	node tr[N*4];
	void modify(int l,int r,int p,int x)
	{
		if(l==r)
		{
			tr[x]=g[pos[p]];
			return;
		}
		int mid=(l+r)/2;
		if(p<=mid) modify(l,mid,p,x*2);
		else modify(mid+1,r,p,x*2+1);
		tr[x]=tr[x*2]*tr[x*2+1];
	} 
	node query(int l,int r,int L,int R,int x)
	{
		if(l>R||r<L) return oo;
		if(l>=L&&r<=R) return tr[x]; 
		int mid=(l+r)/2;
		node lv=query(l,mid,L,R,x*2),rv=query(mid+1,r,L,R,x*2+1);
		if(lv.n==-1) return rv;
		if(rv.n==-1) return lv;
		return lv*rv;
	}
}tr;
int fa[N],dep[N],siz[N],Son[N];
int ed[N],id[N],ids,top[N];
int tag[N];
void dfs1(int now,int f)
{
	fa[now]=f;
	dep[now]=dep[f]+1;
	siz[now]=1;
	int maxx=0;
	for(int i=head[now];i;i=e[i].next)
	{
		int v=e[i].to;
		if(v==f) continue;
		dfs1(v,now);
		siz[now]+=siz[v];
		if(siz[v]>maxx) maxx=siz[v],Son[now]=v;
	}
}
void dfs2(int now,int topf)
{
	++ids;
	id[now]=ids;
	pos[ids]=now;
	ed[topf]=id[now];
	top[now]=topf;
	if(Son[now]) dfs2(Son[now],topf),w[now]=w[Son[now]];
	f[now]=1;
	for(int i=head[now];i;i=e[i].next)
	{
		int son=e[i].to;
		if(son==fa[now]||son==Son[now]) continue;
		dfs2(son,son);
		w[now]=w[now]*w[son]%mod;
		if(!w[son]) tag[now]++;
		else f[now]=f[now]*w[son]%mod;
	}
	w[now]+=a[now],w[now]%=mod;
	g[now].n=g[now].m=2;
	g[now].r[0][0]=f[now],g[now].r[0][1]=a[now],
	g[now].r[1][0]=0,g[now].r[1][1]=1;
	if(tag[now]) g[now].r[0][0]=0;
	tr.modify(1,n,id[now],1);
}
void updata(int x,ll v)
{
	g[x].r[0][1]=v;
	while(x)
	{
		ll last=tr.query(1,n,id[top[x]],ed[top[x]],1).r[0][1];
		tr.modify(1,n,id[x],1);
		ll now=tr.query(1,n,id[top[x]],ed[top[x]],1).r[0][1];
		x=fa[top[x]];
		if(!last) tag[x]--;
		else f[x]=f[x]*inv(last)%mod;
		if(!now) tag[x]++;
		else f[x]=f[x]*now%mod;
		if(tag[x]) g[x].r[0][0]=0;
		else g[x].r[0][0]=f[x];
	}
}
int q;
int main()
{
	oo.n=-1;
	zero.n=zero.m=2;
	zero.r[1][1]=1;
	scanf("%d%d",&n,&q);
	for(int i=2;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		add(x,i);
	}
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	dfs1(1,0);
	dfs2(1,1);
	while(q--)
	{
		int v,x;
		scanf("%d%d",&x,&v);
		updata(x,v);
		printf("%d\n",tr.query(1,n,1,ed[1],1).r[0][1]);
	}
	return 0;
}

标签:int,题解,ll,son,bmatrix,mod,now,abc351g
From: https://www.cnblogs.com/g1ove/p/18163780

相关文章

  • CF1966D Missing Subsequence Sum 题解
    题意:给定\(n(n\le10^6)\)和\(k(k\len)\)。构造一个长度小于等于\(25\)的序列\(a\)满足:1.不存在一个子序列的和为\(k\)。2.对于\(1\lei\len,i\nek\),存在一个子序列的和为\(i\)。看到长度为\(25\),首先肯定会想到二进制。那么我们先构造出一个序列\([2^......
  • ABC351G题解
    考虑动态dp的套路,先树剖一下,令\(son(x)\)为点\(x\)的重儿子。\(g_x=\prod\limits_{u\inC(x)\landu\neqson(x)}f_u\)。于是有\(f_x=f_{son(x)}g_x+a_x\)。于是\(\begin{bmatrix}f_x&1\end{bmatrix}=\begin{bmatrix}f_{son(x)}&1\end{bmatrix}\begin{bmatrix}g_......
  • 【BFS】abc351D Grid and Magnet 题解
    传送门D-GridandMagnet题意:给定h行w列的图表,其中部分位置有磁铁,人物会在磁铁四周((x+1,y),(x-1,y),(x,y+1),(x,y-1))停止,某点的自由度定义为从该点出发最多可到的方块数目可以走重复路前置例题:求连通块大小洛谷P1141思路:由自由度的定义联想到连通块的大小,从而决定用BFS......
  • ABC351_F 题解
    实际上很板。考虑在\(i\)后小于\(val_i\)的数都对答案没贡献,所以我们只需要知道在\(i\)后且大于\(val_i\)的数的和以及有多少个这样的数就可以了。知道了我们要求什么,就可以一眼权值线段树。从后往前扫不断加入数,然后访问对应区间即可,当然因为值域比较大,所以还要离散化......
  • eclipse 题解
    Statement给定一个圆,圆按照顺时针排布着\(2n\)个点,依次编号为\(1\simn\),其中编号为\(1\simn\)的点属于Alice,编号为\((n+1)\sim2n\)的点属于Bob。同时给出两个长度为\(n\)的序列\(A,B\)。你需要确定一个最大的正整数\(K\),使得存在\(K\)个二元组\((x_i,y_i)\)......
  • 题解:洛谷 P1137 旅行计划
    标签:图论,拓扑,dp题意给定一张\(n\)个点\(m\)条边的DAG,对于每个\(i\),求以它为终点最多经过多少个点?思路由于是DAG,求的是终点\(i\)经过的所有点,而刚好拓扑序就满足这个。那么就可以考虑拓扑排序。设\(f_i\)是以\(i\)为终点的最多结点数,那么就有转移方程\(f_v=m......
  • CF1842H Tenzing and Random Real Numbers 题解
    题目链接点击打开链接题目解法实数的概率好反直觉!对\(1\)做限制不是很好做,考虑变成正负性的限制(即对\(0\)做限制)令\(y_i=x_i-0.5\),那么限制就变成了\(y_i+y_j\le0,\;y_i+y_j\ge0\)这里要给出一些实数概率的结论:实数下,\(x=y\)的概率为\(0\),因为\(\frac{1}{\inft......
  • CAUC_CTF 题解
    caucctfwpez_隐写如果计算机是中国人发明的Welcome!easy_rsafromCrypto.Util.numberimport*importgmpy2importlibnumimportrandomimporthashlibn=0x52d483c27cd806550fbe0e37a61af2e7cf5e0efb723dfc81174c918a27627779b21fa3c851e9e94188eaee3d5cd6f7524......
  • [题解]P2015 二叉苹果树
    P2015二叉苹果树树形dp,一般用dfs辅助解决。当我们搜索到\(u\),此时剩下\(cnt\)条边可以用,也就是说\(u\)为根节点的子树最多可以保留\(cnt\)条边。由于上一层的需求,我们显然需要枚举剩余边数\(i\)(\(1\leqi\leqcnt\))。接下来对于每个\(i\),我们考虑剩余的\(u\)条边可以怎么放。......
  • 题解:P10329 [UESTCPC 2024] Add
    Add题意将序列进行一系列的操作,输出对\(a_{1}\)的期望值。题目中操作说的比较明了,再次就不特殊声明了。思路据题意所知,每一个\(n\)应该对应了一个固定的答案。于是我就想到可以打表,就打出了下面的式子。n=1时ans=1n=2时ans=5n=3时ans=14n=4时ans=30n=5时ans=5......