玄学75pts TLE?
  • 板块P6154 游走
  • 楼主Kniqht
  • 当前回复8
  • 已保存回复8
  • 发布时间2022/10/2 20:08
  • 上次更新2023/10/27 09:09:47
查看原帖
玄学75pts TLE?
315205
Kniqht楼主2022/10/2 20:08

萌新刚学期望,开了O2就RE了,但是不知道哪里数组越界了

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+10,mod=998244353;
int n,m,d[N],q[N];
ll f[N],g[N];
int h[N],e[N],ne[N],idx;
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void topsort(){
    int hh=0,tt=-1;
    for(int i=1;i<=n;i++){
        g[i]=1;
        if(!d[i]) q[++tt]=i;
    }
    while(hh<=tt){
        int t=q[hh++];
        for(int i=h[t];~i;i=ne[i]){
            int j=e[i];
            f[j]=((ll)f[j]+f[t]+g[t])%mod;
            g[j]=(g[j]+g[t])%mod;
            if(--d[j]==0)
                q[++tt]=j;
        }
    }
}
ll qpow(ll x,ll p){
    ll res=1;
    while(p){
        if(p&1) res=(res*x)%mod;
        x=(x*x)%mod;
        p>>=1;
    }
    return res%mod;
}
int main(){
    memset(h,-1,sizeof(h));
    scanf("%d%d",&n,&m);
    while(m--){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        d[y]++;
    }
    topsort();
    ll res1=0,res2=0;
    for(int i=1;i<=n;i++) res1=(res1+f[i])%mod,res2=(res2+g[i])%mod;
    ll ans=res1*qpow(res2,mod-2)%mod;
    printf("%lld",ans%mod);
    return 0;
}
2022/10/2 20:08
加载中...