[CSPS2020]T3函数调用题解
本文最后更新于 67 天前,其中的信息可能已经有所发展或是发生改变。

赛上不会的题目。

Before the Beginning

转载请将本段放在文章开头显眼处,如有二次创作请标明。
原文链接:https://www.codein.icu/lp7077/

题解

三种操作:

  1. 单点加
  2. 全局乘
  3. 函数调用
    考虑到这个全局乘看上去就很假,可以考虑用什么全局 tag 维护一下。但这样不可避免需要用到逆元,要是 $0$ 没处理好就挂得不如暴力了。

于是可以处理后缀积,计算一个单点加操作后被乘了多少次。

原本的函数关系是一张有向无环图,将操作三看做依次往外连边即可。

考虑在这张图上处理。

首先用一次 dfs 处理出每个点往下操作会乘上多少倍率。

就是 DAG 上记忆化搜索的做法吧。

此时我们有一个 $O(nm)$ 的做法,对于每一个调用,直接图上搜索过去,搜索过程中维护一个后缀积,然后对操作一点才做真正的更改。

正解感觉很像是把询问的调用也打成标记,然后往下传。

考虑加一个虚点,看做是操作三,然后依次调用询问操作中的调用。

这次似乎需要用拓扑 dp 了,这次的目标是得知每个操作一的倍率。

从根往下推应该就可以了吧,维护每个点被调用多少次。注意操作三的调用顺序,要把后调用的倍率累计进来。

还有个初始值的问题,不想特判,可以考虑塞到图里,看做很多个一开始的加操作。

其实感觉难度不大,只是我太蠢了罢了,赛后可做赛上跳过系列。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <ctype.h>
const int bufSize = 1e6;
inline char nc()
{
    #ifdef DEBUG
    return getchar();
    #endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
template<typename T>
inline T read(T &r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1;
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r *= flag;
}
const int mod = 998244353;
const int maxn = 3e6 + 100;
struct node
{
    int to, next;
} E[maxn];
int head[maxn];
inline void addE(const int& x, const int& y)
{
    static int tot = 0;
    E[++tot].next = head[x], E[tot].to = y, head[x] = tot;
}
inline int add(int x, int y) { int res = x + y; return res >= mod ? res - mod : res; }
inline int mul(int x, int y) { return 1ll * x * y % mod; }
int n, m, q, a[maxn], type[maxn], tar[maxn], w[maxn], S, in[maxn];
int prod[maxn], g[maxn];
void dfs1(int u, int fa)
{
    if(prod[u] != -1) return;
    if (type[u] == 2) prod[u] = w[u];
    else prod[u] = 1;
    for (int p = head[u]; p; p = E[p].next)
    {
        int v = E[p].to;
        if(v == fa) continue;
        dfs1(v, u), prod[u] = mul(prod[u], prod[v]);
    }
}
signed main()
{
    memset(prod, -1, sizeof(prod));
    read(n);
    for (int i = 1; i <= n; ++i) read(a[i]);
    read(m);
    for (int i = 1; i <= m; ++i) 
    {
        read(type[i]);
        if (type[i] == 1) read(tar[i]), read(w[i]);
        else if(type[i] == 2) read(w[i]);
        else 
        {
            int num, x;
            read(num);
            while (num--) read(x), addE(i, x), in[x]++;
        }
    }
    S = n + m + 1;
    for (int i = 1; i <= n; ++i) type[i + m] = 1, tar[i + m] = i, w[i + m] = a[i], addE(S, i + m), in[i + m]++;
    read(q);
    for (int i = 1, x; i <= q; ++i) read(x), addE(S, x), in[x]++;
    dfs1(S, 0);
    static int q[maxn], qt = 0, qh = 1;
    for (int i = 1; i <= S; ++i) if(!in[i]) q[++qt] = i;
    g[S] = 1;
    while(qt >= qh)
    {
        int u = q[qh++];
        for (int p = head[u]; p; p = E[p].next)
        {
            int v = E[p].to;
            g[v] = add(g[v], g[u]), g[u] = mul(g[u], prod[v]);
            if (--in[v] == 0) q[++qt] = v;
        }
    }
    for (int i = 1; i <= n; ++i) a[i] = 0;
    for (int i = 1; i <= S; ++i) if (type[i] == 1) a[tar[i]] = add(a[tar[i]], mul(w[i], g[i]));
    for (int i = 1; i <= n; ++i) printf("%d ", a[i]);
    return 0;
}
本文标题:[CSPS2020]T3函数调用题解
本文作者:Clouder
本文链接: https://www.codein.icu/lp7077/
转载请标明。
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇