正題

題目鏈接:https://www.luogu.com.cn/problem/P7077

---

題目大意

有一些函數分為三種

讓一個位置的數加上一個數

讓所有數乘上一個數

按順序執行一些函數

然后不會有環，按順序調用一些函數，求最后每個位置的數。

---

解題思路

我們發現對于一個乘操作其實就是相當于讓前面的操作多執行若干次。

那么我們可以將一個$3$函數拆成：執行一些函數若干次然后最后乘上一個數。

那么我們可以做一次拓撲排序，然后反著求出每個函數最后乘上的那個數。

之后正著做，對于每個函數我們直接按照輸入順序反著（也就是鄰接表順序）枚舉然后處理出每個函數要被該函數調用多少次，這樣我們可以處理出每個函數的操作次數即可。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=1e5+10,XJQ=998244353; ll redin(){ll x=0,f=1;char c=getchar();while(!(c>='0'&&c<='9')){if(c=='-')f=-f;c=getchar();}while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; } struct node{ll to,next; }a[N*12]; ll n,m,tot,Q,ls[N],w[N],pos[N],val[N]; ll q[N],in[N],z[N],mul[N],ans[N]; void addl(ll x,ll y){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;in[y]++;return; } void topsort(){ll tail=0,head=1;q[++tail]=n;for(ll i=1;i<n;i++)if(!in[i])q[++tail]=i;while(head<=tail){ll x=q[head++];for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;in[y]--;if(!in[y])q[++tail]=y;}}n=tail;return; } int main() {m=redin();for(ll i=1;i<=m;i++)w[i]=redin();n=redin();for(ll i=1;i<=n;i++){ll op=redin();mul[i]=1;if(op==1)pos[i]=redin(),val[i]=redin();else if(op==2)mul[i]=redin();else if(op==3){ll k=redin(),y;for(ll j=1;j<=k;j++){y=redin();addl(i,y);}}}ll cnt=n;mul[++n]=1;Q=redin();while(Q--){ll x=redin();addl(n,x);}topsort();for(ll p=n;p>=1;p--){ll x=q[p];for(ll i=ls[x];i;i=a[i].next)mul[x]=mul[x]*mul[a[i].to]%XJQ;}z[q[1]]=1;for(ll p=1;p<=n;p++){ll x=q[p],g=1;for(ll i=ls[x];i;i=a[i].next){(z[a[i].to]+=z[x]*g%XJQ)%=XJQ;g=g*mul[a[i].to]%XJQ;}}for(ll i=1;i<=cnt;i++)ans[pos[i]]=(ans[pos[i]]+z[i]*val[i]%XJQ)%XJQ;for(ll i=1;i<=m;i++)printf("%lld ",(ans[i]+w[i]*mul[q[1]]%XJQ)%XJQ);return 0; }

總結

以上是生活随笔為你收集整理的P7077-函数调用【拓扑排序,dp】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。