[Leaf] [P7077] 函数调用

p7077-[csp-s-2020]-函数调用---洛谷">P7077 [CSP-S 2020] 函数调用 - 洛谷

1. 题面梗概

中译中：给出一个初始数组，有三类函数：单点加、全局乘、以及按序调用其他函数。给定一个最终的调用序列，求执行完后的数组。

$n, m, q \le 10^5, \sum C_j \le 1e6, \text{Mod} = 998244353$

2. 逻辑推导

最简单的想法就是直接模拟，预期得分 40 pts，考虑从性质入手。

2.1 做法

假如没有操作 $3$，那么就有一种很显然的做法：维护一个乘法标记，记录当前全局已经被乘了多少。接下来的加法都乘上乘法标记的逆元。

假如没有操作2，那么也有一种很显然的做法：函数调用很自然地形成一个DAG，那就建一个DAG出来。

然后从主函数出发进行拓扑排序，递推出每一个函数的调用次数，最后直接处理每个操作 1。

然后有一个很关键的性质，如果某个函数被调用后被乘 $k$，等价于这个函数被执行 $k$ 次。

于是操作 $2$ 和 $3$ 都可以统一转化为改变操作 $1$ 的执行次数。

2.1 乘法转换 $mul[u]$

每个函数执行完，会使全局放大多少倍？

• 操作 1（加法）：$mul[u] = 1$。
• 操作 2（乘法）：$mul[u] = V[u]$。
• 操作 3（调用）：$mul[u] = \prod_{u \to v} mul[v]$。

操作 3 可以通过逆向的拓扑序求解。

2.2 加法统计 $cnt[u]$

对于全局序列中的函数 $f_1, f_2, \dots, f_Q$，最后的函数 $f_Q$ 对前面的函数有乘法影响。

• 逆序处理：设当前后缀乘积为 $prod$。对于 $f_i$，它的有效执行次数 $cnt[f_i] += prod$，随后 $prod = prod \times mul[f_i]$。

• 拓扑：对于调用函数 $u$，其子函数 $v_1, v_2, \dots, v_k$ 被调用的次数受到 $u$ 的 $cnt[u]$ 影响。

  • 最后一个子函数 $v_k$ 被执行的次数就是 $cnt[u]$。

  • 倒数第二个子函数 $v_{k-1}$ 被执行的次数是 $cnt[u] \times mul[v_k]$。

  • 依此类推，利用 拓扑排序 自顶向下下传 $cnt$。

3. 代码实现

▶

AcCode

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 1e5 + 5;
const int mod = 998244353;

vector< int > adj[maxn];
int T[maxn], p[maxn], v[maxn];
ll mul[maxn], cnt[maxn];
// mul 函数的乘法倍数
// cnt 函数的执行次数
int indeg[maxn], seq[maxn];
ll a[maxn];
int n, m, q;

// mul 预处理
ll calc( int u )
{
    if( mul[u] != -1 ) return mul[u];
    if( T[u] == 1 ) return mul[u] = 1;
    if( T[u] == 2 ) return mul[u] = v[u];
    ll res = 1;
    for( int v : adj[u] ) res = res * calc( v ) % mod;
    return mul[u] = res;
}

int main( )
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for( int i = 1; i <= n; ++ i ) cin >> a[i];

    cin >> m;
    for( int i = 1; i <= m; ++ i )
    {
        mul[i] = -1;
        cin >> T[i];
        if( T[i] == 1 ) cin >> p[i] >> v[i];
        else if( T[i] == 2 ) cin >> v[i];
        else 
        {
            int count, child;
            cin >> count;
            for( int j = 1; j <= count; ++ j )
            {
                cin >> child;
                adj[i].push_back(child);
                indeg[child] ++;
            }
        }
    }

    for( int i = 1; i <= m; ++ i ) mul[i] = calc( i );
	
    cin >> q;
    for( int i = 1; i <= q; ++ i ) cin >> seq[i];
	
	// 逆序处理查询序列
    ll prod = 1;
    for( int i = q; i >= 1; -- i ) 
    {
        int f = seq[i];
        cnt[f] = ( cnt[f] + prod ) % mod;
        prod = prod * mul[f] % mod;
    }
    
    queue< int > Q;
    for( int i = 1; i <= m; ++ i ) if( indeg[i] == 0 ) Q.push(i);
	
	// 拓扑排序
    while( !Q.empty( ) )
    {
        int u = Q.front( ); Q.pop( );
        if( T[u] != 3 ) continue;

        ll suf = cnt[u];

        for( int i = adj[u].size( ) - 1; i >= 0; -- i )
        {
            int v = adj[u][i];
            cnt[v] = ( cnt[v] + suf ) % mod;
            suf = suf * mul[v] % mod;
            if( --indeg[v] == 0 ) Q.push(v);
        }
    }

	// 结算部分
    for( int i = 1; i <= n; ++ i )
    {
        a[i] = a[i] * prod % mod;
    }
    
    for( int i = 1; i <= m; ++ i )
    {
        if( T[i] == 1 )
        {
            int idx = p[i];
            a[idx] = ( a[idx] + cnt[i] * v[i] ) % mod;
        }
    }

    for( int i = 1; i <= n; ++ i ) cout << a[i] << ' ';
    return 0;
}

4. 复盘

• 复杂度分析：$O( n + m + q + \sum C_j )$

• 碎碎念：同样是一道找到性质的 拓扑序 DP，我最开始用模拟逆元算的，但是发现这个乘法的逻辑会乱，从而换个角度分析这个问题。

• 关联笔记： 树图DP | 拓扑排序