day2

正睿提高

2018.9.1

---

T1

感觉T1难不了，也没往难处想，一直推结论，找性质，中途刘高吉告诉了我正解，居然用超哥线段树，也没写，凸壳好像能做，但也没写。。。
感觉考试状态不对。
正解：$ax^2+bx = x(ax + b)$，然后就是一些直线了，求一个凸壳，在上面二分，或者直接处理出来。

/*
让b保留符号，x始终为正 
如果是正数，那么axx+bx，就是x(ax+b)，
如果是负数，那么axx-bx，就是x(ax-b)
所以正数就是对所有的ax+b直线做一下凸壳
负数就是对所有的ax-b直线做一下凸壳
然后查询时都带入x的绝对值。 
可以在凸壳上二分（判断交点），但是发现点数不多，所以可以直接处理出来。 
*/
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cctype>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<vector>
using namespace std;
typedef long long LL;
inline int read() {
    int x = 0, f = 1; char ch = getchar(); for (; !isdigit(ch); ch=getchar()) if (ch=='-') f = -1;
    for (; isdigit(ch); ch=getchar()) x = x * 10 + ch - '0'; return x * f;
}
const int N = 500100;
const int M = 32323;
struct Line{
    int a,b;
    bool operator < (const Line &A) const {
        return a == A.a ? b > A.b : a < A.a;
    }
}A[N], q1[N], q2[N]; 
int n;
LL ans[M + M + 100];
double cross(Line A,Line B) {
    return (double)(B.b - A.b) / (double)(A.a - B.a);
}
void work(Line *q,int &Top) {
    q[++Top] = A[1];
    for (int i=2; i<=n; ++i) {
        if (A[i].a == A[i - 1].a) continue; // 斜率相同的保留b最大的 
        while (Top >= 2 && cross(A[i], q[Top - 1]) <= cross(q[Top], q[Top - 1])) Top--;
        q[++Top] = A[i];
    }   
}
int main() {
    n = read(); int Q = read();
    for (int i=1; i<=n; ++i) {
        A[i].a = read(), A[i].b = read();
    }
    int Top1 = 0, Top2 = 0;
    sort(A + 1, A + n + 1);
    work(q1, Top1);
    for (int i=1; i<=n; ++i) A[i].b = -A[i].b;
    sort(A + 1, A + n + 1);
    work(q2, Top2);
    for (int i=1,cur=1; i<=M; ++i) {
        while (cur < Top1 && cross(q1[cur], q1[cur + 1]) <= i) cur ++;
        ans[M + i] = 1ll * q1[cur].a * i * i + 1ll * q1[cur].b * i;
    }
    for (int i=1,cur=1; i<=M; ++i) {
        while (cur < Top2 && cross(q2[cur], q2[cur + 1]) <= i) cur ++;
        ans[M - i] = 1ll * q2[cur].a * i * i + 1ll * q2[cur].b * i;
    }
    while (Q--) {
        int x = read();
        printf("%lld\n",ans[x + M]);
    }
    return 0;
}

//二分代码
void solve(int x,Line *q,int n) {
    int L = 1, R = n - 1, ans = -1;
    while (L <= R) {
        int mid = (L + R) >> 1;
        if (cross(q[mid], q[mid + 1]) <= x) ans = mid, L = mid + 1;
        else R = mid - 1;
    }
    LL Ans;
    if (ans == -1) Ans = 1ll * q[1].a * x * x + 1ll * q[1].b * x;
    else Ans = 1ll * q[ans + 1].a * x * x + 1ll * q[ans + 1].b * x;
    printf("%lld\n",Ans);
}
//询问时这样写
    while (Q--) {
        int x = read();
        if (x < 0) solve(-x, q2, Top2);
        else solve(x, q1, Top1); 
    }

T2

感觉很不可做，直接没怎么看。后悔。
赛后感觉有60分暴力分。

1：暴力转移。
2：记录当前还有多少个1。f[i]表示当期有i个1的期望：
f[0] = 0, f[1] = 1;
然后$f[i] = \frac{1}{i}f[0] + \frac{i-1}{i}f[i-1]$
设初始局面的1的个数为x，逆推，求出f[x]的期望。
3478：只有两个点，那么要不给1号点-1，要不给二号点-1。
然后暴力统计每种答案*它出现的概率，即求它出现的次数。
设a = a[1], b = a[2]。那么答案区间就是a~a+b，因为最后a必须为0
考虑一个答案a+c（a减了a次，b减了c次）出现的次数。
1 1 2 2 1 2 1 1 1 1 这是操作序列，减a的就是1，减b就是2，那么就是将c个2放到n个空隙中，（最后一个一定是1，所以是n个，而不是n+1个），n个空隙，每个空隙放入c个球，然后从所有的n*c个球里面选c个。就是答案的方案数。
正解：
利用期望的线性性，就是求出每一位期望选多少次，然后加起来。
计算每一位期望选多少次，就是和1号一起，1号选完了为止，可以利用3478的做法。复杂度（n*a)。其实这一步计算是可以推出来的。
可以看成在坐标轴的第一象限有一个点(a1,ai)，求走到坐标轴的期望。

$$\sum_{i=0}^{a_i-1}\frac{\binom{a_1-1+i}{i}}{2^{a_1+i}}i+a_i\left(1-\sum_{i=0}^{a_i-1}\frac{\binom{a_1-1+i}{i}}{2^{a_1+i}}\right)$$
第一步是走到了x轴上的某一个点（不能是0），表示ai没有取完，但是a1去完了，所以就结束了。
方案数就是假设走到了往下走了i步，最后走到了(0,ai-i)，对答案的贡献就是i（这一个数选的次数，然后乘上概率，就是期望次数了），然后有多少次i的贡献呢？因为最后只能从走到(0,i)，所以不能在以前走到y轴，只能从(1,i)走到(0,i)，所以就是从(a1,ai)走到(1,ai-i)的走法。就是长为a1-1，高为i的矩阵。一共走(a1-1+i)步，其中往下走i步，所以从中选出i步来的方案数就是总的方案数。除以$2^{a1 + i}$就是概率，在乘以贡献i。
后面的就是ai选完了的贡献了，其概率就是1-ai没选完的概率，贡献就是ai。
发现从i到i+1的时候，就是只增加了一项，所以可以快速求出来。

其实就是a/b，x就是a/b，在模意义下就是a*b的逆元

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cctype>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<vector>
using namespace std;
typedef long long LL;
inline int read() {
    int x = 0, f = 1; char ch = getchar(); for (; !isdigit(ch); ch=getchar()) if (ch=='-') f = -1;
    for (; isdigit(ch); ch=getchar()) x = x * 10 + ch - '0'; return x * f;
}
const int N = 500100;
const LL mod = 323232323;
LL fac[N + N], ifac[N + N], imi[N + N];
LL p[N], pi[N];
int a[N];
LL ksm(int a,int b) {
    LL ans = 1;
    while (b) {
        if (b & 1) ans = 1ll * ans * a % mod;
        a = 1ll * a * a % mod;
        b >>= 1;
    }
    return ans % mod;
}
void init(int n,int lim) {
    fac[0] = 1;
    for (int i=1; i<=lim; ++i) fac[i] = 1ll * fac[i - 1] * i % mod; 
    ifac[lim] = ksm(fac[lim], mod - 2);
    for (int i=lim; i>=1; --i) ifac[i - 1] = 1ll * ifac[i] * i % mod;
    imi[lim] = ksm(ksm(2, lim), mod - 2);
    for (int i=lim; i>=1; --i) imi[i - 1] = 1ll * imi[i] * 2 % mod;
}
LL C(int n,int m) {
    LL t1 = fac[n], t2 = ifac[m], t3 = ifac[n - m];
    return t1 * t2 % mod * t3 % mod;
}
int main() {
    int n = read(), mx = 0;
    for (int i=1; i<=n; ++i) {
        a[i] = read(), mx = max(mx, a[i]);
    }
    init(n, mx + a[1]);
    for (int i=0; i<=mx; ++i) {
        p[i] = 1ll * C(a[1] + i - 1, i) * imi[a[1] + i] % mod;
        pi[i] = 1ll * p[i] * i % mod; // 这两行居然顺序写反了！！！ 
        if (i) p[i] = (p[i] + p[i - 1]) % mod; //  
        if (i) pi[i] = (pi[i] + pi[i - 1]) % mod;
    }
    LL ans = a[1] % mod;
    for (int i=2; i<=n; ++i) 
        ans = (ans + pi[a[i] - 1] + 1ll * (1 - p[a[i] - 1] + mod) * a[i] % mod) % mod;
    cout << ans % mod;
    return 0;
}

T3

考试后半场，由于前两题没写出，就来写这个了。
想到了一个倍增的思路，fu[i][j]表示以i为起点，往上跳$2^j$步的和,和为每个点到i的距离或上a。发现两段区间合并时，只是将一个区间的距离前面加上$2^j$，然后统计这个区间上，第j位有多少个0，就是加上多少个$2^j$。
我想的是树剖统计，统计的复杂度就是$log^2$（树剖一个，线段树/bit一个，（30棵线段树，每一位一个））。然后统计答案的时候，就可以倍增了。写着写着发现了问题，不能统计从一个点向下的答案。（太激动了，一想到就写了，时间也不算很多了，没想到不对就写了，以后注意证明一下思路，看一下是否真的可以处理）。于是就没写出来。

正解：
首先可以在树上差分求一条路径上某一位0的个数可以O(1)，代替树链剖分和线段树那两个log。
然后向上的就是上面写的那样，从lca向下，fd[i][j]表示从i往上$2^j$
步，然后每个点距离f[i][j]的距离或上a，相当于反过来了，然后因为要使i是距离是dis(u,v)，然后依次往上距离减小，所以让i，往上走dis步，然后减去让lca往上走dis(lca,u)步。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cctype>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<vector>
using namespace std;
typedef long long LL;
inline int read() {
    int x = 0, f = 1; char ch = getchar(); for (; !isdigit(ch); ch=getchar()) if (ch=='-') f = -1;
    for (; isdigit(ch); ch=getchar()) x = x * 10 + ch - '0'; return x * f;
}
const int N = 300100;
int f[N][21], cnt[N][21], deth[N], a[N];
LL fu[N][21], fd[N][21]; 
// 因为f[i][j]是往上走2^j步，所以包含了2^j+1个点，所以只保留前面2^j个点，最后一个点不算。
// fu[i][j]为i往上2^j方的点和，对于这所有的2^j个点中的一个k，贡献为dis(k,i)|a[k]，将2^j个点的贡献加起来
// fd[i][j]为i往上2^j方的点和，对于这所有的2^j个点中的一个k，贡献为(dis(k,f[i][j])-1)|a[k]
// 就是将上面的距离反过来，从i开始，距离分别为2^j-1, 2^j-2...0
vector<int> e[N];
void dfs(int u,int fa) {
    deth[u] = deth[fa] + 1;
    f[u][0] = fa;
    for (int i=0; i<=20; ++i) 
        cnt[u][i] = cnt[fa][i] + (!(a[u] & (1 << i))); // 每一位的前缀和 
    for (int sz=e[u].size(),i=0; i<sz; ++i) {
        int v = e[u][i];
        if (v == fa) continue;
        dfs(v, u);
    }
}
int Lca(int u,int v) {
    if (deth[u] < deth[v]) swap(u, v);
    int d = deth[u] - deth[v];
    for (int i=20; i>=0; --i) 
        if (d & (1 << i)) u = f[u][i];
    if (u == v) return u;
    for (int i=20; i>=0; --i)
        if (f[u][i] != f[v][i]) 
            u = f[u][i], v = f[v][i];
    return f[u][0];
}
LL query1(int u,int v) {
    LL res = 0;
    int d = deth[u] - deth[v];
    for (int i=20; i>=0; --i) {
        if (d & (1 << i)) {
            res += fu[u][i];
            u = f[u][i];
            res += 1ll * (1 << i) * (cnt[u][i] - cnt[v][i]); // 上一步的距离增加了2^j，所以多了j位的贡献 
        }
    }
    return res;
}
LL query2(int u,int d) {
    LL res = 0;
    int v = u;
    for (int i=0; i<=20; ++i) { // 正序枚举 先走小的，再走大的，因为实际上是从上面往下走的 
        if (d & (1 << i)) {
            res += fd[v][i];
            res += 1ll * (1 << i) * (cnt[u][i] - cnt[v][i]); // 越往上2^j步，其实下面的也有第j位的贡献，模拟一下 
            v = f[v][i];
        }
    }
    return res;
}
int main() {
    int n = read(), Q = read();
    for (int i=1; i<=n; ++i) a[i] = read();
    for (int i=1; i<n; ++i) {
        int u = read(), v = read();
        e[u].push_back(v), e[v].push_back(u);
    }
    dfs(1, 0);
    for (int i=1; i<=n; ++i) 
        fu[i][0] = fd[i][0] = a[i];
    for (int j=1; j<=20; ++j) 
        for (int i=1; i<=n; ++i) {
            f[i][j] = f[f[i][j-1]][j-1];
            int t1 = f[i][j-1], t2 = f[i][j];
            fu[i][j] = fu[i][j-1] + fu[t1][j-1] + 1ll * (1<<(j-1)) * (cnt[t1][j-1] - cnt[t2][j-1]);
            // 两段区间合并时，上面的一段区间会在二进制下第j-1位上增加一个1，统计这一位多少个0，新增加的这一位的贡献
            // 以前这位是0，然后距离这位也是0，现在距离这位成了1，就是新加的贡献 
            fd[i][j] = fd[i][j-1] + fd[t1][j-1] + 1ll * (1<<(j-1)) * (cnt[i][j-1] - cnt[t1][j-1]);
            // 同理，像上面一样，只不过是下面的一段区间更新。 
        }
    while (Q--) {
        int u = read(), v = read();
        int lca = Lca(u, v), dis = deth[u] + deth[v] - deth[lca] * 2;
        LL Ans = query1(u, f[lca][0]) + query2(v, dis + 1) - query2(lca, deth[u] - deth[lca] + 1);
        // 由于fu[i][j]是跳到了f[i][j]，但是答案却少了f[i][j]的，所以多跳一步。 
        printf("%lld\n",Ans);
    }
    return 0;
}