P7077 函数调用

我好蠢啊。。。

考试的时候不会写，现在看了这么多篇题解还是似懂非懂，所以决定写一下草稿。。。

草稿和题解

就是首先，题目保证了函数不会间接的调用其本身，所以可以直接知道这是一个 \(\text{DAG}\) ，从这个角度去考虑。

然后我们考虑对于两种操作，乘法的操作最后乘一下即可，但是对于加法操作，我们需要知道其之后的乘法对于自己的贡献。

因为要保证复杂度，所以这个东西是不能多次 \(\text{top}\) 来维护的。所以我们考虑如何在 \(\text{DAG}\) 上直接搞这个玩意儿。

我们可以先在每个节点处理出来如果选择他，你可以给后面的节点贡献多少的系数。这个东西一个 \(\text{top}\) 即可。然后可以考虑从后往前更新，用一个变量来维护到目前为止，你已经给整一个全局贡献了多少的变量，然后对于每一个点，在其前面进行的乘法操作也是需要考虑的。

最后再进行一次 \(\text{top}\) 将每个点的系数下传一下，下传的方法和之前类似，同时统计一下加法操作的贡献就可以了。

终于明白了！！！

感悟

高妙，高妙！

感觉自己对于 \(\text{top}\) 排序的理解都加深了。感觉跟有一些 \(\text{DP}\) 的思路有一点像，我们将贡献后置，然后再依次推出当前的系数是多少。

高妙，高妙！

代码

#include<bits/stdc++.h>

using namespace std;

#define Lint long long

inline int read()

{

	char c=getchar();int x=0;

	while(c<'0'||c>'9') c=getchar();

	while('0'<=c&&c<='9') x=x*10+c-'0',c=getchar();

	return x;

}

const int N=1e5+5,M=1e5+5,Q=1e5+5,E=1e6+5;

const Lint MOD=998244353;

int n,m;Lint a[N];int c[Q];

struct Point{Lint mul,coe,add;int tag,pos;}b[M];

struct Edge{int nxt,to;}e[2][E];int fir[2][M],deg[M],size[2];

void add(int u,int v,int tag){e[tag][++size[tag]]=(Edge){fir[tag][u],v},fir[tag][u]=size[tag];}

queue<int> q;

int topn[N],cnt=0;

void top()

{

	for(int i=1;i<=m;++i) if(deg[i]==0) q.push(i);

	while(!q.empty())

	{

		int tmp=q.front();q.pop();

		topn[++cnt]=tmp;

		for(int i=fir[0][tmp];i;i=e[0][i].nxt)

		{

			deg[e[0][i].to]--;

			if(!deg[e[0][i].to]) q.push(e[0][i].to);

		}

	}

}

int opt[Q];

int main()

{

//	freopen("call.in","r",stdin);

//	freopen("call.out","w",stdout);

	n=read();

	for(int i=1;i<=n;++i) a[i]=read();

	m=read();

	for(int i=1;i<=m;++i)

	{

		b[i].tag=read(),b[i].mul=1;

		if(b[i].tag==1) b[i].pos=read(),b[i].add=read();

		if(b[i].tag==2) b[i].mul=read();

		if(b[i].tag==3)

		{

			deg[i]=read();

			for(int j=1,v;j<=deg[i];++j)

			v=read(),add(v,i,0),add(i,v,1);

		}

	}

	top();

	for(int i=1;i<=m;++i)

	{

		for(int j=fir[0][topn[i]];j;j=e[0][j].nxt)

		b[e[0][j].to].mul*=b[topn[i]].mul,b[e[0][j].to].mul%=MOD;

	}

	int q=read();

	for(int i=1;i<=q;++i) c[i]=read();

	Lint now=1;

	for(int i=q;i>=1;--i)

	{

		b[c[i]].coe+=now,b[c[i]].coe%=MOD;

		now*=b[c[i]].mul,now%=MOD;

	}

	for(int i=1;i<=n;++i) a[i]*=now,a[i]%=MOD;

	for(int i=m;i>=1;--i)

	{

		Lint now=1;

		for(int j=fir[1][topn[i]];j;j=e[1][j].nxt)

		{

			b[e[1][j].to].coe+=b[topn[i]].coe*now%MOD,b[e[1][j].to].coe%=MOD;

			now*=b[e[1][j].to].mul,now%=MOD;

		}

	}

	for(int i=1;i<=m;++i)

	{

		if(b[i].tag==1)

		a[b[i].pos]+=b[i].add*b[i].coe%MOD,a[b[i].pos]%=MOD;

	}

	for(int i=1;i<=n;++i) printf("%lld ",a[i]);

	printf("\n");

	return 0;

}

巴特西

P7077 函数调用

草稿和题解

感悟

代码

最新文章

热门文章

巴特西

P7077 函数调用

草稿 和 题解

感悟

代码

最新文章

热门文章

草稿和题解