Gym-101466K Random Numbers（线段树，数学，唯一分解定理）

给一棵树，树上每个节点有一个权值，有两个操作，RAND操作查询u的子树乘积是多少以及有多少因数，SEED操作把节点u乘上v

n，q <= 1e5。数值小于等于1e9，最大的质因数不超过13

组队训练和队友一起写的，写到头昏，代码也是合力完成的，我数学几乎为0，数学部分感谢队友@lllrj抬一手

思路：首先由于乘积的值过大，线段树不能直接维护权值，考虑到查询的是因数个数，所以线段树直接维护2,3,5,7,11,13的指数，乘一个数就是把这个数质因数分解再单点更新，查询就是区间求和，乘积用快速幂计算，至于因数的个数由唯一分解定理可知，把一个数分解质因数变成(x1^n1)*(x2^n2)*(x3^n3)......的形式，因数的个数就是(n1+1)*(n2+1)*(n3+1).....然后两个结果都要对1e9+7取模，比赛时后一个结果忘记取模浪费了快一个小时。。。

建树的话就是按dfs序建树，也是个常见套路，参见HDU-3974。需要注意按dfs序建树之后不能直接用编号的权值去建（比如a【3】不一定在线段树【3,3】这个点上），所以是先建树，输入的时候做更新

AC代码：217ms，29.4MB

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #include<iostream>
  5 #include<vector>
  6 #include<queue>
  7 #include<cmath>
  8 #include<set>
  9 #define lid id<<1
 10 #define rid id<<1|1
 11 #define INF 0x3f3f3f3f
 12 #define LL long long
 13 #define debug(x) cout << "[" << x << "]" << endl
 14 using namespace std;
 15 const int maxn = 1e5+5;
 16 int b[]={2,3,5,7,11,13};
 17 int d[maxn][6]={0};
 18 void cal(int x, int *d)
 19 {
 20     for(int i = 0;i < 6 ;i++){
 21         while(x%b[i]==0)x/=b[i],d[i]++;
 22     }
 23 }
 24 const int mx = 1e5+10;
 25 const int mod = 1e9+7;
 26 int L[mx], R[mx], p[mx];
 27 struct tree{
 28     int l, r;
 29     int p[6]; //2,3,5,7,11,13
 30     int lazy[6];
 31 }tree[mx<<2];
 32 vector<int> G[mx];
 33 int cnt;
 34 LL Ans[6] = {0};
 35 
 36 LL qpow(LL x, LL n){ //x^n
 37     LL res = 1;
 38     while (n > 0){
 39         if (n & 1) res = res*x%mod;
 40         x = x*x % mod;
 41         n >>= 1;
 42     }
 43     return res;
 44 }
 45 
 46 void push_up(int id){
 47     for (int i = 0; i < 6; i++)
 48         tree[id].p[i] = tree[lid].p[i]+tree[rid].p[i];
 49 }
 50 
 51 void build(int l, int r, int id){
 52     tree[id].l = l;
 53     tree[id].r = r;
 54     for (int i = 0; i < 6; i++) tree[id].p[i] = 0;
 55     if (l == r) return;
 56     int mid = (l+r) >> 1;
 57     build(l, mid, lid);
 58     build(mid+1, r, rid);
 59 }
 60 
 61 void dfs(int u){
 62     L[u] = ++cnt;
 63     int len = G[u].size();
 64     for (int i = 0; i < len; i++){
 65         int v = G[u][i];
 66         dfs(v);
 67     }
 68     R[u] = cnt;
 69 }
 70 
 71 void upd(int c, int id, int *x){
 72     if (tree[id].l == c && tree[id].r == c){
 73         for (int i = 0; i < 6; i++)
 74             tree[id].p[i] += x[i];
 75         return;
 76     }
 77     int mid = (tree[id].l + tree[id].r)>>1;
 78     if (c <= mid) upd(c, lid, x);
 79     else upd(c, rid, x);
 80     push_up(id);
 81 }
 82 
 83 void query(int l, int r, int id){
 84     if (tree[id].l == l && tree[id].r == r){
 85         for (int i = 0; i < 6; i++)
 86             Ans[i] += tree[id].p[i];
 87         return;
 88     }
 89     int mid = (tree[id].l + tree[id].r)>>1;
 90     if (r <= mid) query(l, r, lid);
 91     else if (mid < l) query(l, r, rid);
 92     else {
 93         query(l, mid, lid);
 94         query(mid+1, r, rid);
 95     }
 96 }
 97 
 98 int main(){
 99     int n, u, v, a, q;
100     cnt = 0;
101     scanf("%d", &n);
102     for (int i = 1; i < n; i++){
103         scanf("%d%d", &u, &v);
104         G[u].push_back(v);
105         p[v] = u;
106     }
107     for (int i = 0; i < n; i++){
108         if (!p[i]) {
109             dfs(i);
110             break;
111         }
112     }
113     build(1, n, 1);
114     for (int i = 0; i < n; i++){
115         scanf("%d", &a);
116         cal(a,d[i]);
117         upd(L[i], 1, d[i]);
118     }
119     scanf("%d", &q);
120     while (q--){
121         char s[10];
122         int d2[6] = {0};
123         scanf("%s%d", s, &a);
124         if (s[0] =='R'){
125             memset(Ans, 0, sizeof Ans);
126             query(L[a], R[a], 1);
127             LL ans = 1;
128             LL num = 1;
129             for (int i = 0; i < 6; i++){
130                 //debug(Ans[i]);
131                 num = (num*qpow(b[i], Ans[i]))%mod;
132                 ans = ans*(Ans[i]+1)%mod;
133             }
134             printf("%lld %lld
", num, ans);
135         }
136         else {
137             int c;
138             scanf("%d", &c);
139             cal(c, d2);
140             upd(L[a], 1, d2);
141         }
142     }
143     return 0;
144 }

View Code

赛后微调（并没有什么改变）：202ms，27MB

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #include<iostream>
  5 #include<vector>
  6 #include<queue>
  7 #include<cmath>
  8 #include<set>
  9 #define lid id<<1
 10 #define rid id<<1|1
 11 #define INF 0x3f3f3f3f
 12 #define LL long long
 13 #define debug(x) cout << "[" << x << "]" << endl
 14 using namespace std;
 15 
 16 int b[] = {2, 3, 5, 7, 11, 13};
 17 const int mx = 1e5+10;
 18 const int mod = 1e9+7;
 19 int L[mx], R[mx], p[mx];
 20 struct tree{
 21     int l, r;
 22     int p[6];
 23     int lazy[6];
 24 }tree[mx<<2];
 25 vector<int> G[mx];
 26 int cnt = 0;
 27 LL Ans[6] = {0};
 28 
 29 void cal(int x, int *d){
 30     for(int i = 0; i < 6 ; i++){
 31         while(x % b[i] == 0){
 32             x /= b[i];
 33             d[i]++;
 34         }
 35     }
 36 }
 37 
 38 LL qpow(LL x, LL n){ //x^n
 39     LL res = 1;
 40     while (n > 0){
 41         if (n & 1) res = res*x%mod;
 42         x = x*x % mod;
 43         n >>= 1;
 44     }
 45     return res;
 46 }
 47 
 48 void push_up(int id){
 49     for (int i = 0; i < 6; i++)
 50         tree[id].p[i] = tree[lid].p[i]+tree[rid].p[i];
 51 }
 52 
 53 void build(int l, int r, int id){
 54     tree[id].l = l;
 55     tree[id].r = r;
 56     for (int i = 0; i < 6; i++) tree[id].p[i] = 0;
 57     if (l == r) return;
 58     int mid = (l+r) >> 1;
 59     build(l, mid, lid);
 60     build(mid+1, r, rid);
 61 }
 62 
 63 void dfs(int u){
 64     L[u] = ++cnt;
 65     int len = G[u].size();
 66     for (int i = 0; i < len; i++){
 67         int v = G[u][i];
 68         dfs(v);
 69     }
 70     R[u] = cnt;
 71 }
 72 
 73 void upd(int c, int id, int *x){
 74     if (tree[id].l == c && tree[id].r == c){
 75         for (int i = 0; i < 6; i++)
 76             tree[id].p[i] += x[i];
 77         return;
 78     }
 79     int mid = (tree[id].l + tree[id].r)>>1;
 80     if (c <= mid) upd(c, lid, x);
 81     else upd(c, rid, x);
 82     push_up(id);
 83 }
 84 
 85 void query(int l, int r, int id){
 86     if (tree[id].l == l && tree[id].r == r){
 87         for (int i = 0; i < 6; i++)
 88             Ans[i] += tree[id].p[i];
 89         return;
 90     }
 91     int mid = (tree[id].l + tree[id].r)>>1;
 92     if (r <= mid) query(l, r, lid);
 93     else if (mid < l) query(l, r, rid);
 94     else {
 95         query(l, mid, lid);
 96         query(mid+1, r, rid);
 97     }
 98 }
 99 
100 int main(){
101     int n, u, v, a, q;
102     scanf("%d", &n);
103     for (int i = 1; i < n; i++){
104         scanf("%d%d", &u, &v);
105         G[u].push_back(v);
106         p[v] = u;
107     }
108     for (int i = 0; i < n; i++){
109         if (!p[i]) {
110             dfs(i);
111             break;
112         }
113     }
114     build(1, n, 1);
115     for (int i = 0; i < n; i++){
116         int d[6] = {0};
117         scanf("%d", &a);
118         cal(a, d);
119         upd(L[i], 1, d);
120     }
121     scanf("%d", &q);
122     while (q--){
123         char s[10];
124         scanf("%s%d", s, &a);
125         if (s[0] == 'R'){
126             memset(Ans, 0, sizeof Ans);
127             query(L[a], R[a], 1);
128             LL ans = 1, num = 1;
129             for (int i = 0; i < 6; i++){
130                 num = (num*qpow(b[i], Ans[i]))%mod;
131                 ans = ans*(Ans[i]+1)%mod;
132             }
133             printf("%lld %lld
", num, ans);
134         }
135         else {
136             int c;
137             int d2[6] = {0};
138             scanf("%d", &c);
139             cal(c, d2);
140             upd(L[a], 1, d2);
141         }
142     }
143     return 0;
144 }

View Code