这次运气比较好，做出两题。本来是冲着第3题可以cdq分治做的，却没想出来，明天再想好了。
A. On Number of Decompositions into Multipliers
题意：n个数a1，a2, a3...an求n个数相乘与a1*a2*a3*a4...an相等的排列个数。
分析：首先应该对ai分解质因数，求出所有ai中质因数及个数，枚举排列中每个数包含的质因数个数，例如质因数qi，有ni个，相应的排列中数包含质因数qi个数设为x1，x2,....xn, x1+x2+x3..+xn = ni , 那么对于qi共有C(ni+n-1, n-1)种情况。简单来说就是将ni分成n部分，这样想：有ni个球，需要分成n部分，也就是在n个球中插入n-1根木棍，这样分成n部分就相当于ni+n-1中选n-1个位置。最后把所有质因子可能的划分情况相乘起来就行了。
注意：分解质因数最后一个质因数可能很大！
代码：
#include <bits/stdc++.h>
#define in freopen("solve_in.txt", "r", stdin);
#define bug(x) printf("Line %d : >>>>>>>\n", (x));
#define pb push_back using namespace std;
typedef long long LL;
typedef map<int, int> Mps;
const int M = (int)1e9+;
const int maxn = ;
const int maxm = (int)1e5 + ;
LL inv[maxn];
int a[maxn];
Mps Div;
vector<int> dv; LL powmod(LL a, LL b) {
LL res = ;
while(b) {
if(b&)
res = (res*a)%M;
b >>= ;
a = (a*a)%M;
}
return res;
}
void getInv(int n) {
for(int i = ; i < n; i++) {
inv[i] = powmod(i, M-);
}
}
void getDiv(int x) {
int m = (int)sqrt(x+.);
for(int i = ; i <= m; i++) {
if(x%i == ) {
if(Div[i] == )
dv.pb(i);
while(x%i == ) {
Div[i]++;
x/=i;
}
}
}
if(x > ) {
if(Div[x] == )
dv.pb(x);
Div[x]++;
}
}
LL nCr(LL n, LL m) {
LL res = ;
for(int i = ; i < m; i++) {
res = res*(n-i)%M*inv[i+]%M;
if(res < )
res += M;
}
return (res + M)%M;
}
int main() { getInv(maxn);
int n;
scanf("%d", &n);
for(int i = ; i <= n; i++) {
scanf("%d", a+i);
getDiv(a[i]);
}
LL ans = ;
for(int i = ; i < (int)dv.size(); i++) {
int x = dv[i];
ans = ans*nCr(Div[x]+n-, n-)%M;
}
cout<<ans<<endl;
return ;
}
B. On Sum of Fractions
题意：给定n， u(i)表示不超过i的最大质数， v(i)表示大于i的最小质数。求对于所有的2<= i <= n , sum{1/(u(i)*v(i)}， 最简分式结果。
分析：
列出n的前几个数的1/u(i)*v(i)，发现对于两个相邻素数pi, pi+1间的数i， 1/u(i)*v(i)结果是一样的。也就是说 对于 pi <= x < pi+1， sum{1/u(x)v(x)},化简后就是， 1/u(x)-1/v(x), 得到这个结论后，每次找到大于n的一个素数pi+1，结果就变成两部分， x < pi, 和 pi <= x < n， 第一部分化简就是1/2-1/pi ,第二部分：n-pi+1/(pi*pi+1), 两者之和合并一下就会得到一个表达式：2*(n+1)-2*(pi+pi+1)-pi*pi+1/(2*pi*pi+1)。求质数，用Miller-Rabin法判断前后两个质数就可以了。
代码：
#include <bits/stdc++.h>
#define in freopen("solve_in.txt", "r", stdin);
#define bug(x) printf("Line %d : >>>>>>>\n", (x));
#define pb push_back using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
typedef map<int, int> Mps; LL powmod(LL a, LL b, LL c) {
LL res = ;
while(b) {
if(b&) res = res*a%c;
b >>= ;
a = (a*a)%c;
}
return res;
}
bool test(int n, int a, int d) {
if(n == )return true;
if(n == a) return true;
if((n&) == ) return false;
while(!(d&)) d >>= ;
int t = powmod(a, d, n);
while((d != n-) && (t != ) && (t != n-)) {
t = (LL)t*t%n;
d <<= ;
}
return (t == n-) || (d&) == ; }
bool isPrime(int n) {
if(n < ) return false;
int a[] = {, , };
for(int i = ; i <= ; i++) if(!test(n, a[i], n-)) return false;
return true;
}
pair<LL, LL> getPrime(LL n) {
LL x = n;
x++;
PII ans;
while() {
if(isPrime(x)) {
ans.first = x;
break;
}
x++;
}
x = n;
while() {
if(isPrime(x)) {
ans.second = x;
break;
}
x--;
}
return ans;
}
LL getGcd(LL a, LL b) {
return !b ? a : getGcd(b, a%b);
}
int main() { int T;
int n;
for(int t = scanf("%d", &T); t <= T; t++) {
scanf("%d", &n);
if(n == ) {
puts("1/6");
} else {
PII u = getPrime(n);
LL x = u.first, y = u.second;
LL a = *(n+)-*(x+y)+x*y;
LL b = *x*y;
LL c = getGcd(a, b);
printf("%I64d/%I64d\n", a/c, b/c);
}
}
return ;
}
C. On Changing Tree
题意：一棵n个结点的树，n <= 3*10^5, 给定q个操作。两种类型：
1 v x k ，给v及v子树上结点增加x-i*k,i表示子树上离v的距离
2 v，询问v结点上的值。
分析：
经过一上午的使劲YY，终于想到了CDQ分治的做法，其实比普通树状数组做法要慢，而且难写（也可能是我写得太挫了），复杂度最坏可能达到O(n*log^2n).1200ms能过也算是走运。
简要思路：首先将所有操作按照v结点的深度由大到小拍个序，具体分治的时候，对于原始编号在[l，r]的操作，要将它分成两部分，<= m 和>m 部分，然后考虑编号<=m，的修改操作(操作1) 对编号>m的询问操作(操作2)影响，其实也就是用操作1对所有影响的的要询问的结点的值更新。但是又不能针对每一<=m的操作1，去更新可能影响到的>m操作2， 这样复杂度会很高，那么问题关键就在于怎么按照深度的顺序将操作1作用累积起来，每次更新对结点v影响时，只需要考虑v到根节点的路径上最靠近v的一个操作1。
合并两个同一棵子树但是不同深度的操作1的影响时，例如1 v1 x1 k1, 1 v2 x2 k2, dep[v1] <= dep[v2]，将v1合并到v2时，新的x = x1 - (dep[v2]-dep[v1])*k1 + x2, 新的k = k1+k2。同时在询问和更新某个结点v的上方且最靠近的v的操作1对应的结点时是利用线段树维护的，具体是将子树对应的叶节点一一编号，然后看做区间，将对应结点更新时，只需要将该节点的子树包含的叶子节点的区间进行更新，例如v对应叶子节点编号[L,R]只需要将一个标记cover设置为v，表示该段叶子结点对应的子树的根为最新的。这样做的依据是树中每棵子树包含的叶子结点都不同，但是可以连续编号的。
说的有点复杂，还是普通方法简单，这个也只是为了练习CDQ分治。||--
代码：
/*Time 2014 09 01 , 10:22 */
#include <bits/stdc++.h>
#define in freopen("solve_in.txt", "r", stdin);
#define bug(x) printf("Line %d : >>>>>>>\n", (x));
#define lson rt<<1, l, m
#define rson rt<<1|1, m+1, r
#define inf 0x0f0f0f0f
#define pb push_back using namespace std;
typedef long long LL;
const int maxn = *(int)1e5 + ;
const int M = (int)1e9 + ;
vector<int> g[maxn];
int ll[maxn], rr[maxn], dep[maxn], rk[maxn], t1[maxn], t2[maxn];
int cover[maxn<<];
int ans[maxn], x[maxn], k[maxn];
int qN;
int cnt, ct, vis[maxn]; struct Query
{
int type;
int v, x, k; } qu[maxn];
bool cmp(const int &a, const int &b)
{
return dep[qu[a].v] < dep[qu[b].v];
}
void dfs(int u)
{
if(g[u].size() == )
{
ll[u] = rr[u] = ++cnt;
return;
}
else ll[u] = inf, rr[u] = ;
for(int i = ; i < g[u].size(); i++)
{
int v = g[u][i];
dep[v] = dep[u]+;
dfs(v);
ll[u] = min(ll[u], ll[v]);
rr[u] = max(rr[u], rr[v]);
}
}
void pushDown(int rt)
{
if(cover[rt] != -)
{
cover[rt<<] = cover[rt<<|] = cover[rt];
cover[rt] = -;
}
}
void update(int rt, int l, int r, int L, int R, int u)
{
if(L <= l && R >= r)
{
cover[rt] = u;
return;
}
pushDown(rt);
int m = (l+r)>>;
if(L <= m)
update(lson, L, R, u);
if(R > m)
update(rson, L, R, u);
}
void query(int rt, int l, int r, int L, int R)
{
if(cover[rt] != -)
{
qN = cover[rt];
return;
}
pushDown(rt);
int m = (l+r)>>;
if(L <= m)
query(lson, L, R);
if(qN == - && R > m)
query(rson, L, R);
return;
}
void solve(int l, int r)
{
if(l >= r)
{
return;
}
int m = (l+r)>>;
t1[] = t2[] = ;
for(int i = l; i <= r; i++)
{
if(rk[i] <= m)
{
t1[++t1[]] = rk[i];
}
else
{
t2[++t2[]] = rk[i];
}
}
queue<int> q1, q2;
for(int i = l; i <= r; i++)
{
if(i <= m)
{
rk[i] = t1[i-l+];
if(qu[rk[i]].type == )
{
q1.push(rk[i]);
}
}
else
{
rk[i] = t2[i-m];
if(qu[rk[i]].type == )
q2.push(rk[i]);
}
}
cover[] = ;
ct++;
while(!q2.empty())
{
int xx = q2.front();
q2.pop();
int v1 = qu[xx].v;
while(!q1.empty() && dep[qu[q1.front()].v] <= dep[v1])
{
int yy = q1.front();
q1.pop();
int v2 = qu[yy].v;
int x2 = qu[yy].x;
int k2 = qu[yy].k;
qN = -;
query(, , cnt, ll[v2], rr[v2]);
x[v2] = (x2+x[qN])%M-(LL)(dep[v2]-dep[qN])%M*(LL)k[qN]%M;
if(x[v2] < ) x[v2] += M;
k[v2] = (k2+k[qN])%M;
update(, , cnt, ll[v2], rr[v2], v2);
}
qN = -;
query(, , cnt, ll[v1], rr[v1]);
ans[xx] = ((ans[xx]+x[qN])%M-(LL)(dep[v1]-dep[qN])%M*(LL)k[qN]%M+M)%M;
}
solve(l, m);
solve(m+, r);
}
int main()
{ int n, q;
scanf("%d", &n);
for(int i = ; i <= n-; i++)
{
int u = i+, v;
scanf("%d", &v);
g[v].pb(u);
}
dep[] = ;
dfs();
scanf("%d", &q);
for(int i = ; i <= q; i++)
{
rk[i] = i;
scanf("%d", &qu[i].type);
if(qu[i].type == )
{
scanf("%d%d%d", &qu[i].v, &qu[i].x, &qu[i].k);
}
else scanf("%d", &qu[i].v);
}
sort(rk+, rk+q+, cmp);
// for(int i = 1; i <= q; i++)
// cout<<qu[rk[i]].v<<endl;
solve(, q);
for(int i = ; i <= q; i++)
{
if(qu[i].type == )
{
printf("%d\n", ans[i]);
}
}
return ;
}