求正解

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

by gyh20 @ 2020-11-08 10:33:53

将操作建成 DAG 计算每个加法操作被之后的乘法操作乘了几次。

民间数据 AC 代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int read(){
    int t=0;char v=getchar();
    while(v<'0'||v>'9')v=getchar();
    while(v>='0'&&v<='9')t=(t<<3)+(t<<1)+v-48,v=getchar();
    return t;
}
const int M=998244353;
void add(int &x,int y){(x+=y)>=M?x-=M:x;}
int t,a[1000002],n,k,head[1000002],opt[1000002],m,val[1000002],rd[1000002],pos[1000002],cnt,b[1000002],c[1000002],num[1000002],d[1000002],v;
struct edge{int to,next;}e[2000002];
void addd(int x,int y){e[++cnt]=(edge){y,head[x]},head[x]=cnt;++rd[y];}
void dfs(int x){
    if(~b[x])return;
    b[x]=1;
    if(opt[x]==1)return;
    if(opt[x]==2){
        b[x]=val[x];
        return;
    }
    for(int i=head[x];i;i=e[i].next)dfs(e[i].to),b[x]=1ll*b[x]*b[e[i].to]%M;
}
queue<int>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){
        opt[i]=read();
        if(opt[i]==1)pos[i]=read(),val[i]=read();
        else if(opt[i]==2)val[i]=read();
        else{
            k=read();
            for(int j=1;j<=k;++j){
                int x=read();
                addd(i,x);
            }
        }
    }memset(b,-1,sizeof(b));
    for(int i=1;i<=m;++i)dfs(i);
    k=read();
    for(int i=1;i<=k;++i)c[i]=read();
    v=1;
    for(int i=k;i;--i){
        if(opt[c[i]]==1)add(num[c[i]],v);
        else if(opt[c[i]]==2)v=1ll*v*val[c[i]]%M;
        else{
            add(num[c[i]],v);
            v=1ll*v*b[c[i]]%M;
        }
    }
    for(int i=1;i<=n;++i)a[i]=1ll*a[i]*v%M;
    for(int i=1;i<=m;++i)if(!rd[i])q.push(i);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        if(opt[x]==2)continue;
        if(opt[x]==1){
            add(a[pos[x]],1ll*num[x]*val[x]%M);
            continue;
        }
        int vv=1;
        for(int i=head[x];i;i=e[i].next){
            add(num[e[i].to],1ll*vv*num[x]%M);
            if(!(--rd[e[i].to]))q.push(e[i].to);
            vv=1ll*vv*b[e[i].to]%M;
        }
    }
    for(int i=1;i<=n;++i)printf("%d ",a[i]);
}

by gyh20 @ 2020-11-08 10:36:13

@mikechu

by mikechu @ 2020-11-08 10:36:52

@Fee_clе6418 先%为敬

by mikechu @ 2020-11-08 10:37:34

那加法次数会不会很多呢？

by mikechu @ 2020-11-08 10:37:46

@Fee_clе6418

by gyh20 @ 2020-11-08 10:38:52

@mikechu 总共只有 m 个操作啊

by mikechu @ 2020-11-08 10:39:19

一个操作如果调用很多次加法函数呢？

by gyh20 @ 2020-11-08 10:41:19

@mikechu 在操作上打上标记，最后一遍拓扑排序推到最底层

by gyh20 @ 2020-11-08 10:41:46

代码应该比较好理解

by mikechu @ 2020-11-08 10:42:04

emmm...