昨天的CF自己太挫了。一上来看到A题，就有思路，然后马上敲，但是苦于自己很久没有敲计数的题了，许多函数都稍微回忆了一阵子。A题的主要做法就是将每个数质因数分解，统计每个质因子的个数，对于每个质因子pi的个数k，等价于解一个方程x1+x2+...+xn=k的有多少个非负整数解，学过离散数学或者一些组合数学的就会知道，答案是C(k,n+k-1)，但是由于n+k-1可能会很大，我一开始考虑小了，贡献了好多次RE，所以在算组合数的时候只能算出每个数的阶乘以及对应的逆元去算，然后将每个因子算出来的结果乘起来就可以了。
B的话写一下就会发现很明显的能够裂项，所以问题就转换成求u(n),v(n),n的大小达到10^9，但是基于素数的稠密性我们可以在有限的时间内算出来，10^11以内的相邻素数间隔貌似是在400多还是500多，每次判素数的复杂度是根号n，所以大致找出u(n),v(n)的时间是在10^7以内，这个在CF上绝对是可以算的，知道u,v后面的就是简单的计算一下。当然为了加快速度，可以考虑素性测试。
C的话拿到的时候时间不多了，想了一下就有了思路，但是10分钟真的打不出来，于是就想想算了。今天才打出来的。在树上对结点以及它的后代进行更新自然是先把这棵树搜成dfs序列，但是像题目这种，隔一层－k的怎么办呢？ 可以考虑建两棵线段树，首先预处理出每棵树的深度dep,每次更新的时候就在第一棵线段树上每个结点加上x+k*dep[v]，然后再在第二棵线段树上加上-k。 那么询问的时候怎么办呢？ 询问的时候的答案就是 该结点在第一棵线段树上的值ans1,加上在第二棵线段树上的值ans2乘上对应结点的深度 即 ans1+ans2*dep[v]。可以优化的地方是其实并不需要建两棵，只是一棵线段数维护两个值而已，我写的这份代码很慢，1.9s，差不多都超时了，不过也没有办法啦。
|
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 |
#pragma warning(disable:4996)#include<iostream>#include<cstring>#include<string>#include<algorithm>#include<cstdio>#include<vector>#include<cmath>#include<map>#define maxn 300500#define ll long long#define mod 1000000007using
namespace std;struct
Node{ int
l, r; ll add, sum;};struct
SegmentTree{ Node N[4 * maxn]; void
build(int
i, int
L, int
R) { N[i].l = L; N[i].r = R; N[i].sum = N[i].add = 0; if
(L == R){ return; } int
M = (L + R) >> 1; build(i << 1, L, M); build(i << 1 | 1, M + 1, R); } void
pushDown(int
i) { ll tt = N[i].add; if
(N[i].l == N[i].r) return; if
(tt != 0){ (N[i << 1].add += tt) %= mod; (N[i << 1 | 1].add += tt) %= mod; (N[i << 1].sum += (N[i << 1].r - N[i << 1].l + 1)*tt%mod) %= mod; (N[i << 1 | 1].sum += (N[i << 1 | 1].r - N[i << 1 | 1].l + 1)*tt%mod) %= mod; N[i].add = 0; } } void
pushUp(int
i) { N[i].sum = (N[i << 1].sum + N[i << 1 | 1].sum) % mod; } void
add(int
i, int
L, int
R, ll s) { if
(N[i].l == L&&N[i].r == R){ (N[i].add += s) %= mod; (N[i].sum += (R - L + 1)*s) %= mod; return; } pushDown(i); int
M = (N[i].l + N[i].r) >> 1; if
(R <= M) add(i << 1, L, R, s); else
if (L > M) add(i << 1 | 1, L, R, s); else
add(i << 1, L, M, s), add(i << 1 | 1, M + 1, R, s); pushUp(i); } ll query(int
i, int
L, int
R) { if
(N[i].l == L&&N[i].r == R){ return
N[i].sum; } pushDown(i); int
M = (N[i].l + N[i].r) >> 1; if
(R <= M) return
query(i << 1, L, R); else
if (L > M) return
query(i << 1 | 1, L, R); else
return query(i << 1, L, M) + query(i << 1 | 1, M + 1, R); //pushUp(i); }}st[2];int
n;vector<int> G[maxn];int
dep[maxn];int
pre[maxn];int
post[maxn];int
dfs_clock;void
dfs(int
u, int
fa,int
d){ pre[u] = ++dfs_clock; dep[u] = d; for
(int i = 0; i < G[u].size(); i++){ int
v = G[u][i]; if
(v == fa) continue; dfs(v, u, d + 1); } post[u] = dfs_clock;}int
main(){ while
(cin >> n) { for
(int i = 0; i <= n; i++) G[i].clear(); int
vi; for
(int i = 2; i <= n; i++){ scanf("%d", &vi); G[vi].push_back(i); G[i].push_back(vi); } dfs_clock = 0; dfs(1, -1, 0); st[0].build(1, 1, n); st[1].build(1, 1, n); int
q; scanf("%d", &q); ll vq, xq, kq; int
tq; for
(int i = 0; i < q; i++){ scanf("%d", &tq); if
(tq == 1){ scanf("%I64d%I64d%I64d", &vq, &xq, &kq); st[0].add(1, pre[vq], post[vq], (xq + dep[vq] * kq)%mod); st[1].add(1, pre[vq], post[vq], -kq); } else{ ll ans = 0; scanf("%d", &vq); ans = (ans + st[0].query(1, pre[vq], pre[vq])) % mod; ans = (ans + st[1].query(1, pre[vq], pre[vq])*dep[vq]) % mod; ans = (ans + mod) % mod; printf("%I64d\n", ans); } } } return
0;} |
CodeForces369C On Changing Tree,布布扣,bubuko.com
CodeForces369C On Changing Tree
原文：http://www.cnblogs.com/chanme/p/3571783.html