湖南seo网站多少钱,青岛网站建设企业,二手房信息发布平台,lol福利wordpress昨天的CF自己太挫了。一上来看到A题#xff0c;就有思路#xff0c;然后马上敲#xff0c;但是苦于自己很久没有敲计数的题了#xff0c;许多函数都稍微回忆了一阵子。A题的主要做法就是将每个数质因数分解#xff0c;统计每个质因子的个数#xff0c;对于每个质因子pi的… 昨天的CF自己太挫了。一上来看到A题就有思路然后马上敲但是苦于自己很久没有敲计数的题了许多函数都稍微回忆了一阵子。A题的主要做法就是将每个数质因数分解统计每个质因子的个数对于每个质因子pi的个数k等价于解一个方程x1x2...xnk的有多少个非负整数解学过离散数学或者一些组合数学的就会知道答案是C(k,nk-1)但是由于nk-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,每次更新的时候就在第一棵线段树上每个结点加上xk*dep[v]然后再在第二棵线段树上加上-k。 那么询问的时候怎么办呢 询问的时候的答案就是 该结点在第一棵线段树上的值ans1,加上在第二棵线段树上的值ans2乘上对应结点的深度 即 ans1ans2*dep[v]。可以优化的地方是其实并不需要建两棵只是一棵线段数维护两个值而已我写的这份代码很慢1.9s差不多都超时了不过也没有办法啦。 #pragma warning(disable:4996)
#includeiostream
#includecstring
#includestring
#includealgorithm
#includecstdio
#includevector
#includecmath
#includemap
#define maxn 300500
#define ll long long
#define mod 1000000007
using 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 LN[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 LN[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;
vectorint 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;
}转载于:https://www.cnblogs.com/chanme/p/3571783.html
