信行散记

但行好事，莫问前程

0%

csps2020函数调用

发表于

https://www.luogu.com.cn/problem/P7077

40pts

暴力模拟即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 10e5 + 10, M = 998244353;
int arr[N], n, m, Q;
int flag = 1;

struct Func1
{
	int p, v;
	Func1(int p, int v) : p(p), v(v) {}
};

struct Func2
{
	int v;
	Func2(int v) : v(v) {}
};

struct Func3
{
	vector<int> v;
	Func3() {}
};

vector<Func1> f1;
vector<Func2> f2;
vector<Func3> f3;
int mp[N], md[N];

void calc(int k, int p) // 模拟执行 fk 中的第 p 个 函数
{
	if(k == 1)
	{
		Func1 & f = f1[p];
		if(f.v % flag == 0) arr[f.p] = (f.v / flag + arr[f.p]) % M;
		else
		{
			for(int i = 1; i <= n; i++)
				arr[i] = (arr[i] * flag) % M;
			flag = 1;
			arr[f.p] = (arr[f.p] + f.v) % M;
		}
	}
	else if(k == 2) flag = (flag * f2[p].v) % M;
	else
	{
		Func3 & f = f3[p];
		for(vector<int>::iterator it = f.v.begin(); it != f.v.end(); it++)
			calc(md[*it], mp[*it]);
	}
}

signed main(void)
{
	scanf("%lld", &n);
	for (int i = 1; i <= n; i++)
		scanf("%lld", arr + i);

	scanf("%lld", &m);
	for (int i = 1; i <= m; i++)
	{
		scanf("%lld", md + i);
		if (md[i] == 1)
		{
			mp[i] = f1.size();
			int p, v;
			scanf("%lld%lld", &p, &v);
			f1.push_back(Func1(p, v));
		}
		else if (md[i] == 2)
		{
			mp[i] = f2.size();
			int v;
			scanf("%lld", &v);
			f2.push_back(Func2(v));
		}
		else if (md[i] == 3)
		{
			mp[i] = f3.size();
			int c, x;
			scanf("%lld", &c);
			Func3 tmp;
			for (int l = 1; l <= c; l++)
				scanf("%lld", &x),
					tmp.v.push_back(x);
			f3.push_back(tmp);
		}
	}

	Func3 fAns;
	int Q, x;
	scanf("%lld", &Q);
	for(int i = 1; i <= Q; i++)
	{
		scanf("%lld", &x);
		fAns.v.push_back(x);
	}
	f3.push_back(fAns);
	calc(3, f3.size() - 1);

	for(int i = 1; i <= n; i++) cout << (flag * arr[i]) % M << " ";
}

满分做法

主要是“将一个操作转化为另一个操作”的思想.

我们发现当只有操作1的时候，答案可以直接计算而不需要处理

所以我们就把所有操作都转化为操作1

假如没有操作2，那么：

建一个DAG出来

把输入数据里被调用的QQ个函数连接成一个主函数，将它的调用次数设为11

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

然后,

某个函数被调用后序列被乘k，等价于这个函数被执行k次

于是操作2或3的情况都可以统一转化成改变操作1的执行次数

于是就结束了…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 10, P = 998244353;

int n, m, Q;
vector<int> G1[N], G2[N];

int deg2[N], cnt[N], data[N], tp[N], mul[N], add[N], pos[N], deg1[N];
void topo1()
{
    static queue<int> q;
    for (int i = 0; i <= m; ++i)
    {
        deg1[i] = G2[i].size();
        if (deg1[i] == 0)
            q.push(i);
    }
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = 0; i != G1[u].size(); ++i)
        {
            int v = G1[u][i];
            mul[v] = (long long)mul[v] * mul[u] % P;
            --deg1[v];
            if (deg1[v] == 0)
                q.push(v);
        }
    }
}

void topo2()
{
    static queue<int> q;
    for (int i = 0; i <= m; ++i)
    {
        deg2[i] = G1[i].size();
        if (deg2[i] == 0)
            q.push(i);
    }
    while (!q.empty())
    {
        int u = q.front();
        int now_mul = 1;
        q.pop();
        for (int i = G2[u].size(); i != 0; --i)
        {
            int v = G2[u][i - 1];
            cnt[v] = (cnt[v] + (long long)cnt[u] * now_mul) % P;
            now_mul = (long long)now_mul * mul[v] % P;
            --deg2[v];
            if (deg2[v] == 0)
                q.push(v);
        }
    }
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", data + i);
    scanf("%d", &m);
    mul[0] = 1;
    for (int i = 1; i <= m; ++i)
    {
        scanf("%d", &tp[i]);
        if (tp[i] == 1)
        {
            scanf("%d", &pos[i]), scanf("%d", &add[i]);
            mul[i] = 1;
        }
        if (tp[i] == 2)
        {
            scanf("%d", &mul[i]);
        }
        if (tp[i] == 3)
        {
            mul[i] = 1;
            int len;
            scanf("%d", &len);
            for (int j = 0; j < len; ++j)
            {
                int v;
                scanf("%d", &v);
                G1[v].push_back(i);
                G2[i].push_back(v);
            }
        }
    }
    scanf("%d", &Q);
    cnt[0] = 1;
    for (int i = 0; i < Q; ++i)
    {
        int x;
        scanf("%d", &x);
        G2[0].push_back(x);
        G1[x].push_back(0);
    }
    topo1(), topo2();
    for (int i = 1; i <= n; ++i)
        data[i] = (long long)data[i] * mul[0] % P;

    for (int i = 1; i <= m; ++i)
        if (tp[i] == 1)
            data[pos[i]] = (data[pos[i]] + (long long)cnt[i] * add[i]) % P;
    for (int i = 1; i <= n; ++i)
        printf("%d ", data[i]);
}

欢迎关注我的其它发布渠道