Problem Statement

We are given an array a of length n and m operations. There are three types of operations:

1. Addition: Given x and y, increase a[x] by y.
2. Multiplication: Given x, multip all elements in a by x.
3. Function Call: Given k operation indices c_1, c_2, ..., c_k, execute the operations c_1, c_2, ..., c_k in sequence.

The problem guarantees that no function call creates a cycle (i.e., the graph of operations is a DAG). We are also given a final function call (operation 0) that triggers the entire sequence of operations. The task is to compute the final state of the array a after all operations have been executed.

Analysis

The key observation is that the operations form a Directed Acyclic Graph (DAG). Each operation is a node, and a function call (operation 3) creates directed edges from the calling operation to the called operations. Since there are no cycles, we can use topological sorting to process the operations in a valid order.

To solve the problem, we need to determine two things for each operation:

• Operation Count (cnt): How many times the operation is executed.
• Multiplication Factor (mul): The cumulative multiplication effect of all multiplication operations (operation 2) that are executed.

Let's break down the problem into simpler cases:

1. Only Addition (Operation 1): This is straightforward; we simply add the values.
2. Addition and Function Calls (Operations 1 and 3): We can use topological sorting to compute the execution count of each operation. For each element a[i], we sum the contributions of all addition operations affecting i, multiplied by their respective execution counts.
3. Multiplication and Function Calls (Operations 2 and 3): We need to compute the total multiplication factor for the entire sequence. This is equivalent to computing the multiplication factor for each multiplication operation and then multiplying all these factors together.
4. Addition and Multiplication (Operations 1 and 2): Each addition operation's contribution is multiplied by the product of all subsequent multiplication operations. We can compute this by processing the operations in reverse order.

Combining all three operations, we need to compute both cnt and mul for each operation. The execution count of an operation depends on the operations that call it. Specifically, for an operation i with called operations c_1, c_2, ..., c_k, the execution count of c_j is increased by the execution count of i multiplied by the product of the multiplication factors of the operations c_{j+1}, c_{j+2}, ..., c_k.

Thus, for each operation i, we maintain two values: cnt_i (execution count) and mul_i (multiplication factor). The contribution of operation i to its called operation c_j is given by:

cnt_{c_j} += cnt_i * (mul_{c_{j+1}} * mul_{c_{j+2}} * ... * mul_{c_k})

We can compute mul_i using a depth-first search (DFS) that propagates multiplication factors from child operations to parent operations. Then, we use topological sorting to compute cnt_i by processing operations in topological order and applying the above formula.

Implementation

First, we build the graph representing the operations and their dependencies. We use an adjacency list to store the graph.

Next, we perform a DFS to compute the multiplication factor mul for each operation. If an operation is a multiplication (type 2), its mul is its value. Otherwise, it's the product of the mul values of its called operations.

After computing mul, we calculate the in-degrees of each node to prepare for topological sorting. We only consider nodes that are part of the graph (i.e., have been visited during the DFS).

We then perform a topological sort. We start with the root operation (operation 0) and process each node. For each called operation, we update its execution count based on the current operation's execution count and the product of the multiplication factors of the subsequent called operations. We traverse the called operations in reverse order to efficiently compute the product of subsequent multiplication factors.

Finally, we apply the operations to the initial array. We multiply each element of the array by the multiplication factor of the root operation. Then, for each addition operation, we add its contribution (value multiplied by its execution count) to the corresponding element in the array.

Code

#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <functional>

using namespace std;

const int MAXN = 100005;
const long long MOD = 998244353;

struct Operation {
    int type;
    int index;
    long long value;
};

vector<int> graph[MAXN];
long long initial_array[MAXN];
long long multiplication_factor[MAXN];
bool visited[MAXN];
long long operation_count[MAXN];
Operation operations[MAXN];

void compute_multiplication_factors(int current_node) {
    if (visited[current_node]) {
        return;
    }
    visited[current_node] = true;

    if (operations[current_node].type == 2) {
        multiplication_factor[current_node] = operations[current_node].value;
    } else {
        multiplication_factor[current_node] = 1;
    }

    for (int child : graph[current_node]) {
        compute_multiplication_factors(child);
        multiplication_factor[current_node] = (multiplication_factor[current_node] * multiplication_factor[child]) % MOD;
    }
}

void build_in_degrees(int num_operations) {
    for (int i = 0; i <= num_operations; ++i) {
        if (visited[i]) {
            for (int child : graph[i]) {
                operation_count[child]++;
            }
        }
    }
}

void perform_topological_sort(int root_operation, int num_operations) {
    queue<int> q;
    q.push(root_operation);
    operation_count[root_operation] = 1;

    while (!q.empty()) {
        int current_node = q.front();
        q.pop();

        long long suffix_product = 1;
        if (graph[current_node].empty()) {
            continue;
        }

        for (auto it = graph[current_node].rbegin(); it != graph[current_node].rend(); ++it) {
            int child = *it;
            operation_count[child] = (operation_count[child] + operation_count[current_node] * suffix_product % MOD) % MOD;
            suffix_product = (suffix_product * multiplication_factor[child]) % MOD;

            operation_count[child]--;
            if (operation_count[child] == 0) {
                q.push(child);
            }

            if (it == graph[current_node].rend() - 1) {
                break;
            }
        }
    }
}

void apply_operations(int array_size, int num_operations) {
    for (int i = 1; i <= array_size; ++i) {
        initial_array[i] = (initial_array[i] * multiplication_factor[0]) % MOD;
    }

    for (int i = 1; i <= num_operations; ++i) {
        if (operations[i].type == 1) {
            int index = operations[i].index;
            long long value = operations[i].value;
            initial_array[index] = (initial_array[index] + value * operation_count[i] % MOD) % MOD;
        }
    }

    for (int i = 1; i <= array_size; ++i) {
        cout << initial_array[i] << " ";
    }
    cout << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int array_size, num_operations, num_calls;
    cin >> array_size;
    for (int i = 1; i <= array_size; ++i) {
        cin >> initial_array[i];
    }

    cin >> num_operations;
    for (int i = 1; i <= num_operations; ++i) {
        cin >> operations[i].type;
        if (operations[i].type == 1) {
            cin >> operations[i].index >> operations[i].value;
        } else if (operations[i].type == 2) {
            cin >> operations[i].value;
        } else {
            int num_called;
            cin >> num_called;
            for (int j = 0; j < num_called; ++j) {
                int called_operation;
                cin >> called_operation;
                graph[i].push_back(called_operation);
            }
        }
    }

    cin >> num_calls;
    for (int i = 0; i < num_calls; ++i) {
        int called_operation;
        cin >> called_operation;
        graph[0].push_back(called_operation);
    }

    compute_multiplication_factors(0);
    build_in_degrees(num_operations);
    perform_topological_sort(0, num_operations);
    apply_operations(array_size, num_operations);

    return 0;
}