2017 ACM-ICPC, Universidad Nacional de Colombia Programming Contest

字数统计: 4.6k字   |   阅读时长: 24分
训练题解
solved A B C D E F G H I J K
11 / 11 O O O O O O Ø O Ø O Ø
  • O：比赛时通过
  • Ø：赛后通过
  • !：比赛时尝试了未通过
  • ·：比赛时未尝试

比赛链接

A. Rooms and Passages

Solved by Sstee1XD. 3:44(+)

题意： 一堆数字，从中选两个进行没有进制的加分，问其中的最小值和最大值。

思路： 把所有数字转换成长度相等的字符串，补前置00。越前面的数字对数字大小的贡献越大，所以每次都贪心地凑前面的数字即可。要同时和很多数字进行计算，那么搞一个字典树即可。

AC代码 
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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e7 + 10;
const int M = 1e6 + 7;
const ll INF = 0x3f3f3f3f3f3f3f3f;

int n, maxLen;
ll m[M];
int dig[M][21];

void get(ll m, int i) {
	ll val = m;
	int len = 0;
	ll last;
	while (len < maxLen) {
		len++;
		last = m % 10;
		m /= 10;
		dig[i][len] = last;
	}
}

void getlen(ll m) {
	int len = 0;
	while (m) {
		len++;
		m /= 10;
	}
	if (len > maxLen) maxLen = len;
}


struct Trie{
	struct Node {
		int nx[11], cnt;
		void init() {
			memset(nx, -1, sizeof(nx));
			cnt = 0;
		}
	}t[N];
	int root, tot;
	int newnode() {
		t[++tot].init();
		return tot;
	}
	int init() {
		tot = 0;
		root = newnode();
	}
	void insert(int id) {
		int now = root;
		for (int i = maxLen; i >= 1; --i) {
			int v = dig[id][i];
			if (t[now].nx[v] == -1) t[now].nx[v] = newnode();
			now = t[now].nx[v];
			t[now].cnt++;
		}
	}
	ll queryMax(int id) {
		int now = root;
		ll res = 0;
		for (int i = maxLen; i >= 1; --i) {
			int v = dig[id][i];
			int maxx = -1;
			int to = -1;
			for (int j = 0; j <= 9; ++j) {
				if (t[now].nx[j] != -1 && t[ t[now].nx[j] ].cnt) {
					if ((v + j) % 10 > maxx) maxx = (v + j) % 10, to = j;
				}
			}
			now = t[now].nx[to];
			res = res * 10 + maxx;
		}
		return res;
	}
	ll queryMin(int id) {
		int now = root;
		ll res = 0;
		for (int i = maxLen; i >= 1; --i) {
			int v = dig[id][i];
			int minn = 10;
			int to = -1;
			for (int j = 0; j <= 9; ++j) {
				if (t[now].nx[j] != -1 && t[ t[now].nx[j] ].cnt) {
					if ((v + j) % 10 < minn) minn = (v + j) % 10, to = j;
				}
			}
			now = t[now].nx[to];
			res = res * 10 + minn;
		}
		return res;
	}
	void del(int id) {
		int now = root;
		for (int i = maxLen; i >= 1; --i) {
			int v = dig[id][i];
			now = t[now].nx[v];
			t[now].cnt--;
		}
	}
}trie;

void run () {
	trie.init();
	maxLen = 1;
	ll maxx = -INF;
	ll minn = INF;
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%lld", &m[i]);
		getlen(m[i]);
	}
	for (int i = 1; i <= n; ++i) {
		get(m[i], i);
		trie.insert(i);
	}
	for (int i = 1; i <= n; ++i) {
		trie.del(i);
		maxx = max(maxx, trie.queryMax(i));
		minn = min(minn, trie.queryMin(i));
		trie.insert(i);
	}
	printf("%lld %lld\n", minn, maxx);
}

int main () {
	run();
	return 0;
}

B - Maximum Tree

solved by lllllan. 00:16(+)

题意： 分配树上每一层节点的孩子节点数量，使得树上节点数最大。

AC代码 
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
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 40;

ll a[maxn];

bool cmp (ll a, ll b) { return a > b; }

void run () {
	int n;
	scanf("%d", &n);
	
	for (int i = 1; i <= n; ++i) scanf("%lld", a + i);
	sort(a + 1, a + n + 1, cmp);
	
	ll ans = 1;
	ll tem = 1;
	for (int i = 1; i <= n; ++i) {
		ans += (tem *= a[i]);
	}
	printf("%lld\n", ans);
}

int main () {
	run();
	return 0;
}

C - Planet Communcation

solved by Tryna.0:55(+)

题解： 三维判断点是否在直线上

AC代码 
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
#include<bits/stdc++.h>

using namespace std;

const int maxn = 5e3 + 10;
const double eps = 1e-8;
int sgn(double x) {
	if(fabs(x) < eps) return 0;
	if(x < 0) return -1;
	else return 1;
}

struct Point3{
	double x, y, z;
	Point3(double _x = 0, double _y = 0, double _z = 0) {
		x = _x;
		y = _y;
		z = _z;
	}
	double len() {
		return sqrt(x * x + y * y + z * z);
	}
	Point3 operator - (const Point3 &b) const{
		return Point3(x - b.x, y - b.y, z - b.z);
	}
	double operator * (const Point3 &b) const{
		return x * b.x + y * b.y + z * b.z;
	}
	Point3 operator ^ (const Point3 &b)const{
		return Point3(y * b.z - z * b.y, z * b.x - x * b.z, x * b.y - y * b.x);
	}
	double distance(const Point3 &b) const{
		return sqrt((x - b.x) * (x - b.x) + (y - b.y) * (y - b.y) + (z - b.z) * (z - b.z));
	}
}P[maxn];

struct Line3{
	Point3 s, e;
	Line3(Point3 _s, Point3 _e) {
		s = _s;
		e = _e;
	}
	double dispointtoline(Point3 p) {
		return ((e - s) ^ (p - s)).len() / s.distance(e);
	}
//	bool pointonseg(Point3 p) {
//		return sgn(((s - p) ^ (e - p)).len()) == 0 && sgn((s - p) * (e - p)) == 0;
//	}
};
int n, vis[maxn];
void run () {
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) {
		scanf("%lf %lf %lf", &P[i].x, &P[i].y, &P[i].z);
	}
	int sum = 0;
	for(int i = 2; i <= n; i++) {
		if(vis[i]) continue;
		Line3 l = Line3(P[1], P[i]);
		vis[i] = 1;
		for(int j = i + 1; j <= n; j++) {
			if(vis[j]) continue;
//			printf("%d %d %f\n", i, j, l.dispointtoline(P[j]));
			if(l.dispointtoline(P[j]) == 0) {
				vis[j] = 1;
			}
		}
		sum++;
	}
	printf("%d\n", sum);
}

int main () {
	run();
	return 0;
}

D - Double it

solved by Tryna.0:08(+)

题解： 水题，不断除二就行

AC代码 
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
#include<bits/stdc++.h>

using namespace std;

const int maxn = 2e5 + 10;

int n;
string s;
void run () {
	scanf("%d", &n);
	s = "";
	while(n) {
		if(n % 2 == 0) {
			s += 'B';
			n = (n - 2) / 2;
		}
		else {
			s += 'A';
			n = n / 2;
		}
	}
	reverse(s.begin(), s.end());
	cout<<s<<endl;
}

int main () {
	run();
	return 0;
}

E. Text Editor

Solved by Sstee1XD. 2:06(+3)

题意： 在模式串中求最长前缀串，使其在文本串中至少出现nn次。

思路： 二分长度，用kmpkmp进行checkcheck即可。

AC代码 
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
#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

char a[N], b[N];
int lena, lenb;
int nxt[N];
int n;

void getNxt() {
	int i = 0;
	int j = nxt[0] = -1;
	while (i < lenb) {
		while (j != -1 && b[i] != b[j]) j = nxt[j];
		nxt[++i] = ++j;
	}
}

int kmp() {
	int i = 0, j = 0;
	int ans = 0;
	getNxt();
	while (i < lena) {
		while (j != -1 && a[i] != b[j]) j = nxt[j];
		i++, j++;
		if (j >= lenb) {
			j = nxt[j];
			ans++;
		}
	}
	return ans;
}

bool check() {
	return kmp() >= n;
}

void run () {
	scanf("%[^\n]", a);
	lena = strlen(a);
	getchar();
	scanf("%[^\n]", b);
	lenb = strlen(b);
	scanf("%d", &n);
	int l = 1, r = lenb, mid;
	while (l <= r) {
		mid = l + r >> 1;
		lenb = mid;
		if (check()) {
			l = mid + 1;
		} else {
			r = mid - 1;
		}
	}
	if (!r) {
		puts("IMPOSSIBLE");
	} else {
		b[r] = 0;
		printf("%s", b);
	}
}

int main () {
	run();
	return 0;
}

F - Polygon Triangles

solved by Tryna.0:23(+)

题解： 水题，判断所有三角形是否合法即可

AC代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 10;
int n, a, b, c;
void run () {
	scanf("%d", &n);
	int flag = 0;
	for(int i = 1; i <= n; i++) {
		scanf("%d %d %d", &a, &b, &c);
		if(flag == 1) continue;
		if(a >= b + c || b >= a + c || c >= a + b) flag = 1;
	}
	puts(flag ? "NO" : "YES");
}

int main () {
	run();
	return 0;
}

G - Generative Model

solved by Tryna.(-)

题意： 给出一个正整数，首先要对这个数进行质因数分解，然后将这些数字拼接成一个字符串。我们现在有两种操作：

  • 拿出一个数字，转化为相应的字母(a = 1, b = 2…)
  • 拿出两个数字，也转化为相应的字母，数字范围[10, 26]

问我们最终能拼接成的字符串的数目。

题解： 通过基本的数论知识，我们可以知道最终字符串的长度不会很长。因为n<1e6n < 1e^6, 所以就算质因数全为最小的22,显然不会超过2020位。所以我们考虑状压dp，枚举每个数字的状态。

AC代码 
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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define LL __int128
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define mp(a,b) make_pair(a,b)
#define PAUSE system("pause");
const double eps = 1e-8;
const int maxn = 2e5 + 10;
const int mod = 1e9 + 7;
int n, sz, dp[(1<<20) + 10];
vector<int>s;
void cal(ll x) {
    for(ll i = 2; i * i <= x; i++) {
		while(x % i == 0) {
			int tmp = i;
			while(tmp) {
				s.pb(tmp % 10);
				tmp /= 10;
			}
			x /= i;
		} 
    }
    if(x > 1) {
		while(x) {
			s.pb(x % 10);
			x /= 10;
		}
	}
}

int dfs(int state) {
	if(dp[state] != -1) return dp[state];
	if(state == (1 << sz) - 1) return 1;
	ll ans = 0;
	int vis[30] = {};
	for(int i = 0; i < sz; i++) {
		if(state & (1 << i) || s[i] == 0) continue;
		if(!vis[s[i]]) {
			vis[s[i]] = 1;
			ans = (ans + dfs(state | (1 << i))) % mod;
		}
		for(int j = 0; j < sz; j++) {
			if(i == j || (state & (1 << j))) continue;
			int x = s[i] * 10 + s[j];
			if(x >= 10 && x <= 26 && !vis[x]) {
				vis[x] = 1;
				ans = (ans + dfs(state | (1 << i) | (1 << j))) % mod;
			}
		}
	}
	return dp[state] = ans;
}

void solve(){
	while(~scanf("%d", &n)) {
		s.clear();
		memset(dp, -1, sizeof(dp));
		cal(n);
		sz = s.size();
		printf("%d\n", dfs(0));
	}
}

int main() {
	int t = 1;
	// scanf("%d", &t);
	// cin>>t;
	while(t--)
		solve();
	return 0;
}


solved by lllllan. 00:06(+)

题意 hello world

AC代码 
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
#include<bits/stdc++.h>

using namespace std;

const int maxn = 2e5 + 10;

void run () {
	int n;
	scanf("%d", &n);
	
	for (int i = 1; i <= n; ++i) {
		if (i == 1) {
			printf("*");
			for (int j = 2; j < n; ++j) printf(" ");
			printf("* ");
			for (int j = 1; j <= n; ++j) printf("*");
			puts("");
		} else if (i == n) {
			for (int j = 1; j <= n; ++j) printf("*");
			printf(" *");
			for (int j = 2; j < n; ++j) printf(" ");
			printf("*");
			puts("");			
		} else {
			printf("*");
			for (int j = 2; j < n; ++j) printf(" ");
			printf("* *");
			for (int j = 2; j < n; ++j) printf(" ");
			puts("*");
		}
	}
}

int main () {
	run();
	return 0;
}

I - Math Class

solved by lllllan. (-)

题意： 给定nn个数字，要求将这些数字分配到两个班里，要求如下

  • 回文数可以分到一个班
  • 只含4或7的幸运数字可以分到一个班
  • 同时满足以上两个条件可以任选一个班（只能选一）
  • 每个数字在该班里，必须要有一个朋友，eg:数字a[i]和a[j]，当∣i−j∣\vert{i-j}\rvert<=k时两个数字属于朋友范畴

判断是否能将所以数字都分到某个班里，并且每个数字至少有一个朋友。

题解： 对于只属于回文数的、只属于幸运数字的，分班是没有疑问的；既不属于回文数、又不属于幸运数字的，无法分班就不可能完成任务了。所以需要考虑哪些“摇摆数字”（即使回文数又是幸运数字，可以选择去其中一个班级）。对于摇摆数字的班级选择，我们考虑搜索。

  • 第一维状态，位置or下标。
  • 对于某个摇摆数，理论上可以任意选择某个班加入，但是为了加入的那个班能找到朋友，或者去成为某个班里某个孤独的数字的朋友。某一位摇摆数的班级选择，还要看其他位数字的“脸色”。增设两维状态，分别记录A班和B班的前一位数字，距离这一位有多少距离（下标差）。
  • 再细致一些，增设两维状态分别记录AB两个班前一位数字是否已经匹配到了朋友。

大致上定义状态dp[pos][preA][preB][isA][isB]用来表示，递归到当前pos位时，A班的最后一个数字距离我们preA的距离，他isA ？ 有 ： 无朋友。B班最后一个数字距离我们preB的距离，他isB ？ 有： 无朋友。值为true或false表示当前的分班方案能过满足题目要求。

搜索细节：

  • 当preA=k and isA=false时，就一定需要给他分配朋友了，但是如果当前pos位不能进入A班，表示当前搜索的方案不能满足题意要求。preB和isB同理。
  • 某一位pos选择了A班之后进入下一步递归，则应将preA更新为1，isA根据前一次的preA和k的关系判断他是否已经有朋友。而preB则需要+1，但是因为k有上限，我们不需要记录一个太大距离，只要一个k+1表示超出朋友范畴即可
  • 没想到最重要的卡住空间复杂度，用一手bitset<maxn> dp[][][][]比bool类型都还能小一半空间
AC代码 
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
#include <bits/stdc++.h>
using namespace std;

inline int rd() {
    int s = 0, w = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
        s = s * 10 + ch - '0', ch = getchar();
    return s * w;
}

const int maxn = 1e5 + 2;
// #define maxn 100010

int check1(int x) {
    while (x) {
        int k = x % 10;
        x /= 10;
        if (k == 4 || k == 7)
            continue;
        return 0;
    }
    return 1;
}

int check2(int x) {
    int q[12] = {0};
    while (x) {
        int k = x % 10;
        x /= 10;
        q[++q[0]] = k;
    }
    for (int i = 1; i <= q[0]; ++i) {
        if (q[i] == q[q[0] - i + 1])
            continue;
        return 0;
    }
    return 2;
}

int n, k;
int a[maxn];

bitset<maxn> vis[25][25][2][2];
bitset<maxn> dp[25][25][2][2];

int dfs(int pos, int preA, bool isA, int preB, bool isB) {
    if ((!isA && preA > k) || (!isB && preB > k)) {
        vis[preA][preB][isA][isB][pos] = 1;
        return dp[preA][preB][isA][isB][pos] = 0;
    }
    if (pos > n) {
        return isA && isB;
    }

    if (vis[preA][preB][isA][isB][pos])
        return dp[preA][preB][isA][isB][pos];
    vis[preA][preB][isA][isB][pos] = 1;

    int flag = 0;
    if (a[pos] & 1) {
        flag |= dfs(pos + 1, 1, preA <= k ? 1 : 0, min(preB, k) + 1, isB);
    }

    if (a[pos] & 2) {
        flag |= dfs(pos + 1, min(preA, k) + 1, isA, 1, preB <= k ? 1 : 0);
    }
    return dp[preA][preB][isA][isB][pos] = flag;
}

void run() {
    n = rd(), k = rd();

    bool flag = 1;
    for (int i = 1; i <= n; ++i) {
        int x = rd();
        a[i] |= check1(x);
        a[i] |= check2(x);
        flag &= (a[i] > 0);
    }
    memset(vis, 0, sizeof vis);
    if (flag == 0)
        return (void)(printf("NO\n"));
    printf("%s\n", dfs(1, k + 1, 1, k + 1, 1) ? "YES" : "NO");
}

int main() {
    run();
    return 0;
}

J. Jeronimo’s List

Solved by Sstee1XD. 1:41(+5)

题意： 计算出序列后，问整个序列中第kk小的数。

思路： 卡了快排，计数排序即可。写的时候数组里面套了个数组一直TT，不知道为啥。

AC代码 
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
#include<bits/stdc++.h>

using namespace std;
#define rg register
const int N = 3e7 + 7;
const int mod = 3e7;

void chmod(int &a) {
	if (a >= mod) a -= mod;
}

inline int rd() {
	int x = 0; int f = 0; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) f |= (ch == '-');
	for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
	if (f) x = -x;
	return x;
}

int a[N], num[N], rk[N];
int n, m, q;

void run () {
	n = rd();m = rd();q = rd();
	for (rg int i = 1; i <= m; ++i) {
		a[i] = rd();
	}
	for (rg int i = m + 1; i <= n; ++i) {
		a[i] = a[i - m] + a[i - m + 1];
		chmod(a[i]);
	}
	for (rg int i = 1; i <= n; ++i) {
		num[ a[i] ]++;
	}
	int tot = 0;
	for (rg int i = 0; i < N; ++i) {
		while (num[i]--) {
			rk[++tot] = i;
		}
	}
	for (rg int i = 1; i <= q; ++i) {
		int u = rd();
		printf("%d\n", rk[u]);
	}
}

int main () {
	run();
	return 0;
}

K. Random Numbers

solved by lllllan. (-)

题意： 树上每个点都有一个权值。两种操作，询问：求以k节点为根的子树的权值乘积、以及这个乘积的约数个数；修改，k节点的权值乘以val。

题解： 单点修改，子树查询 —— 单点修改，区间查询 – DFS序+线段树张手就来。但是，，怎么求乘积和约束个数？

  • 题目保证，每个的权值wiw_i和所有修改的乘数valval，其最大质因数为13.
  • 以质因数作为切入口，所有权值都能拆分成若干个质因数的乘积，因此在线段树的节点上，我们记录每个权值的{1,3,5,7,11,13}每个质因数的个数，方便合并，容易求得乘积。
  • 至于这个乘积的约数个数，我百度一个性质：

假设一个数可以拆分成质因数x1.x2..xkx_1.x_2..x_k，且这些质因数的个数为cnt1.cnt2..cntkcnt_1.cnt_2..cnt_k。那么这个数的约数个数=(cnt1+1)∗(cnt2+1)∗...∗(cntk+1)=(cnt_1 + 1)*(cnt_2 + 1)*...*(cnt_k + 1)

AC代码 
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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 1e5 + 10;
const ll mod = 1e9 + 7;

#define lrt rt << 1
#define rrt rt << 1 | 1
#define pll pair<ll, ll>
#define vec vector<int> 
#define fi first
#define se second

int cnt, head[maxn];
struct edge { int v, next; } e[maxn << 1];
void add (int u, int v) {
	e[++cnt] = {v, head[u]}, head[u] = cnt;
	e[++cnt] = {u, head[v]}, head[v] = cnt;
}

int dfn;
int L[maxn], R[maxn];
int a[maxn], w[maxn];
void dfs (int u, int fa) {
	L[u] = ++dfn;
	w[ L[u] ] = a[u];
	for (int i = head[u]; i; i = e[i].next) {
		int v = e[i].v;
		if (v == fa) continue;
		dfs(v, u);
	}
	R[u] = dfn;
}

struct node {
	int l, r;
	int self[8], base[8];
	int mid () { return l + r >> 1; }
} T[maxn << 2];

int prime[] = {2, 3, 5, 7, 11, 13};
void init (int rt, int &k) {
	for (int i = 0; i < 6; ++i) {
		while (k > 1 && k % prime[i] == 0) {
			T[rt].base[i]++;
			T[rt].self[i]++;
			k /= prime[i];
		}
	}
}

void up (int rt) {
	for (int i = 0; i < 6; ++i) {
		T[rt].base[i] = T[rt].self[i] + T[lrt].base[i] + T[rrt].base[i];
	}
}

void build (int l, int r, int rt) {
	T[rt].l = l, T[rt].r = r;
	for (int i = 0; i < 6; ++i) T[rt].self[i] = T[rt].base[i] = 0;
	
	if (l == r) return (void)(init(rt, w[l]));
	
	int mid = T[rt].mid();
	build(l, mid, lrt);
	build(mid + 1, r, rrt);
	up(rt);
}

vec operator+(const vec A, const int B[]) {
	vec ans(8);
	for (int i = 0; i < 6; ++i) ans[i] = A[i] + B[i];
	return ans;
}
void update (int k, int rt) {
	if (T[rt].l == T[rt].r && T[rt].l == k) return (void)(init(rt, w[k]));
	
	int mid = T[rt].mid();
	if (k <= mid) update(k, lrt);
	if (k >  mid) update(k, rrt);
	up(rt);
}

vec ans(8);
void query (int l, int r, int rt) {
	if (T[rt].l >= l && T[rt].r <= r) return void(ans = ans + T[rt].base);
	
	int mid = T[rt].mid();
	if (l <= mid) query(l, r, lrt);
	if (r >  mid) query(l, r, rrt);
}

ll qpow (ll a, ll n) {
	ll ans = 1;
	while (n) {
		if (n & 1) ans = (ans * a) % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return ans;
}
pll get () {
	ll sum = 1, cnt = 1;
	for (int i = 0; i < 6; ++i) {
		if (ans[i] == 0) continue;
		sum = (sum * qpow(prime[i], (ll)ans[i])) % mod;
		cnt = (cnt * (ans[i] + 1)) % mod;
	}
	return {sum, cnt};
}

int main () {
	
	int n; scanf("%d", &n);
	
	for (int i = 1; i < n; ++i) {
		int u, v; scanf("%d%d", &u, &v);
		add(u, v);
	}
	
	for (int i = 0; i < n; ++i) scanf("%d", a + i);
	dfs(0, 0);
	build(L[0], R[0], 1);
	
	int q; scanf("%d", &q);
	while (q--) {
		char s[10]; scanf("%s", s);
		if (s[0] == 'R') {
			int k; scanf("%d", &k);
			for (int i = 0; i < 6; ++i) ans[i] = 0;
			query(L[k], R[k], 1);
			pll res = get();
			printf("%lld %lld\n", res.fi, res.se);
		} else {
			int k, val; scanf("%d%d", &k, &val);
			w[ L[k] ] *= val;
			update(L[k], 1);
		}
	}
	
	return 0;
}
文章目录
  1. A. Rooms and Passages
  2. B - Maximum Tree
  3. C - Planet Communcation
  4. D - Double it
  5. E. Text Editor
  6. F - Polygon Triangles
  7. G - Generative Model
  8. H - Logo
  9. I - Math Class
  10. J. Jeronimo’s List
  11. K. Random Numbers
|