求正解

mikechu @ 2020-11-08 10:31:35

by Binah @ 2020-11-08 10:57:10

@Fee_clе6418 我也是类似的方法QAQ拓扑序预处理每一个操作会对前面所有加法操作带来多少倍的贡献.然后r数组记录这个贡献,然后拓扑倒序再把标记下放一遍...WA55分

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mod 998244353
#define N 1000002
//suppose there is node m+1.
//we want the result of m+1
int n,m;
vector<int>mp[N];//the sons
int lks[N];
vector<int>fa[N];//the fas
int lkf[N];
int typ[N];//type of every node
int p[N],va[N];//pos and val of add
int r[N];//the product after every node
int laz[N];//lazytags
int a[N];//a
int tmp;
int T;
queue<int>q;
void init()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    scanf("%lld",&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%lld",&typ[i]);
        r[i]=1;
        if(typ[i]==1)
        {
            scanf("%lld%lld",&p[i],&va[i]);
        }
        if(typ[i]==2)
        {
            scanf("%lld",&r[i]);
        }
        if(typ[i]==3)
        {
            scanf("%lld",&T);
            while(T--)
            {
                scanf("%lld",&tmp);
                mp[i].push_back(tmp);
                fa[tmp].push_back(i);
                lkf[i]++;
                lks[tmp]++;
            }
        }
    }
    scanf("%lld",&T);
    while(T--)
    {
        scanf("%lld",&tmp);
        mp[m+1].push_back(tmp);
        fa[tmp].push_back(m+1);
        lkf[m+1]++;
        lks[tmp]++;
    }
    r[m+1]=1;
}
void bfsr()//get the array r
{
    for(int i=1;i<=n;i++)
    {
        if(!mp[i].size())
        {
            q.push(i);
        }
    }
    while(!q.empty())
    {
        int now=q.front();
        //printf("bfs %lld\n",now);
        q.pop();
        for(int i=0;i<fa[now].size();i++)
        {
            r[fa[now][i]]=1ll*r[fa[now][i]]*r[now]%mod;
            lkf[fa[now][i]]--;
            if(!lkf[fa[now][i]])
            {
                q.push(fa[now][i]);
            }
        }
    }
    //for(int i=1;i<=m+1;i++)
    //{
    //  printf("%lld ",r[i]);
    //}
}
void pre()//we move the defult array
{
    for(int i=1;i<=n;i++)
    {
        a[i]=1ll*a[i]*r[m+1]%mod;
    }
}
bool vis[N];
void bfs()//the bfs of solveing
{
    for(int i=1;i<=m;i++)
    {
        if(!lks[i])
        {
            q.push(i);
        }
    }
    laz[m+1]=1;
    q.push(m+1);
    int tmp,now;
    int v;
    while(!q.empty())
    {
        now=q.front();
        q.pop();
        //printf("bfs %lld %lld\n",now,laz[now]);
        for(int i=mp[now].size()-1;i>=0;i--)
        {
            v=mp[now][i];
            laz[v]=(0ll+laz[v]+laz[now])%mod;
            laz[v]%=mod;
            laz[now]=1ll*r[v]*laz[now]%mod;
            lks[v]--;
            if(!lks[v])
            {
                q.push(v);
            }
        }
        if(typ[now]==1)
        {
            a[p[now]]=(long long)((1ll*va[now]*laz[now]%mod+a[p[now]])%mod);
        }
    }
}
void ans()
{
    for(int i=1;i<=n;i++)
    {
        printf("%lld ",a[i]);
    }
}
signed main()
{
    //freopen("call.in","r",stdin);
    //freopen("call.out","w",stdout);
    init();
    bfsr();
    pre();
    bfs();
    ans();
}

by Mivik @ 2020-11-08 11:40:20

@Fee_clе6418 一样的做法

by gyh20 @ 2020-11-08 11:43:06

@Mivik 但我考场代码记搜哪里不是清的 -1 直接用的 0，乘 0 我就当场爆炸。。。。

by Mivik @ 2020-11-08 11:45:28

@Fee_clе6418 标个 vis 不麻烦吧（

by gyh20 @ 2020-11-08 11:46:22

@Mivik 偷懒习惯了。。。。。

by gyh20 @ 2020-11-08 11:46:54

已经强制自己不压行了，但还是低级失误死掉了

by VOILinK @ 2020-11-14 10:03:20

@Fee_clе6418 ~b[i]是神马意思？

by gyh20 @ 2020-11-14 14:39:38

@kuai_zhilin 不是-1

by VOILinK @ 2020-11-15 15:46:28

@Fee_clе6418 蟹蟹QAQ