后：day2

衢州

http://zhengruioi.com/blogof/gaolinxiang/blog/208
2018.8.5

---

预计：50+20+40
实际：50+20+0

T1

开场太困了，简直无法思考。
先做T2，直到最后来再看的时候，发现怎么做了。
想的是用线段树，很麻烦，其实用前缀和就好了。

T2

先写了暴力，然后发现还有个部分分 是 只有一条边大于等于1，感觉可做，于是写了两个小时多，20分，然后还没过。推错式子了。
$C_m^x C_m^y S^{x+y} (n-S)^{m-x+m-y}$

T3

NTT模版忘了，于是暴力，忘记取模。

总结：

1、由于T1开始没想出来，T2写了两个多小时，无果，心态有点炸。
2、考试策略不对，一个小时时应该先暂时放弃T2
3、做题顺序。

---

T1

先统一处理朝向一边的，然后处理朝向另一边的时候，看它与刚才统计的有多少相交的，减去即可。

#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 = 100000;
struct Node{
    int x,y,c,d;
}A[N + 100];
int sum1[N + N + 100], sum2[N + N + 100];
bool vis[N + N + 100];
int n;
bool cmp1(Node A,Node B) {
    return A.c < B.c;
}
int getlen1(int x) {
    if (x <= 0) x = -x;
    return n - x;
}
int getlen2(int x) {
    if (x > n + 1) x = n + 1 - (x - (n + 1)); //注意！！！ 
    int len = x - 1;
    x -= 2;
    if (x & 1) return len - (sum1[x + N] - sum1[-x - 1 + N]);
    else return len - (sum2[x + N] - sum2[-x - 1 + N]);
}
int main() {
    n = read();int m = read();
    for (int i=1; i<=m; ++i) {
        A[i].x = read(), A[i].y = read();
        A[i].c = A[i].y - A[i].x; A[i].d = A[i].x + A[i].y;
    }
    sort(A + 1, A + m + 1, cmp1);
    int now = 1 - n;
    LL Ans = 0;
    for (int i=1; i<=m; ++i) {
        if (A[i].c < now) continue;
        while (now < A[i].c) {
            if (now & 1) sum1[now + N] = sum1[now - 2 + N];
            else sum2[now + N] = sum2[now - 2 + N];
            now ++;
        }
        if (now & 1) sum1[now + N] = 1 + sum1[now - 2 + N];
        else sum2[now + N] = 1 + sum2[now - 2 + N];
        Ans += getlen1(now);
        now ++;
    }
    while (now <= n - 1) {
        if (now & 1) sum1[now + N] = sum1[now - 2 + N];
        else sum2[now + N] = sum2[now - 2 + N];
        now ++;
    }
    for (int i=1-n; i<n; ++i) // 这里不要忘了 
        if (i & 1) sum2[i + N] = sum2[i - 1 + N];
        else sum1[i + N] = sum1[i - 1 + N];
    for (int i=1; i<=m; ++i) {
        if (vis[A[i].d]) continue;
        vis[A[i].d] = true;
        Ans += getlen2(A[i].d);
    }
    cout << 1ll * n * n - Ans;
    return 0;
}

T2

利用期望的线性性，可以分别计算每一条边的概率。
其实答案最后就是求方案数 * 贡献，所以可以枚举每一条边的贡献计算。
每种配对方案，一定是将左边的 男 / 女同学优先和右边的 女 / 男同学配对。我们设这条边断开后两个联通块的大小为 $size0$ 和 $size1$，则经过它的贡献为：

$$\sum_{i=0}^{m}\sum_{j=0}^{m}(\min(i, m-j)+\min(m-i, j))\times C^i_mC^j_m\times size_0^i\cdot size_1^{m-i}\cdot size_0^j\cdot size_1^{m-j}$$
前面是贡献，中间的组合数为选了那几个人，后面是站的位置。
然后发现
$$\sum_{i=0}^{m}\sum_{j=0}^{m}(\min(i, m-j)+\min(m-i, j))\times C^i_mC^j_m \tag{1}$$
这一块只和ijm有关，可以预处理。
$$size_0^{i+j}\cdot size_1^{m+m-i-j}\tag{2}$$
后面的化简后就之和i+j有关。

所以预处理f[k]为k=i+j的(1)式贡献（所有i+j=k的(1)式的和），然后对于每一条边(2)式就是可以O(m)计算了。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cctype>
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 = 3010;
const int mod = 1e9 + 7;
int head[N], nxt[N << 1], to[N << 1], len[N << 1], siz[N], Enum;
LL C[N][N], f[N << 1], P[N][N + N];
LL Answer;
int n, m;
void add_edge(int u,int v,int w) {
    ++Enum; to[Enum] = v; len[Enum] = w; nxt[Enum] = head[u]; head[u] = Enum;
    ++Enum; to[Enum] = u; len[Enum] = w; nxt[Enum] = head[v]; head[v] = Enum;
}
void dfs(int u,int fa) {
    siz[u] = 1;
    for (int i=head[u]; i; i=nxt[i]) {
        int v = to[i];
        if (v == fa) continue;
        dfs(v, u);
        siz[u] += siz[v];
        for (int j=0; j<=m+m; ++j) {
            LL t = 1ll * len[i] * f[j] % mod;
            Answer = (Answer + t * P[siz[v]][j] % mod * P[n-siz[v]][m+m-j] % mod) % mod;
        }
    }
}
void init() {
    for (int i=1; i<=n; ++i) {
        P[i][0] = 1;
        for (int j=1; j<=m+m; ++j) {
            P[i][j] = 1ll * P[i][j - 1] * i % mod;
        }
    }
    C[0][0] = 1;
    for (int i=1; i<=m; ++i) {
        C[i][0] = 1;
        for (int j=1; j<=i; ++j) {
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
        }
    }
    for (int i=0; i<=m; ++i) {
        for (int j=0; j<=m; ++j) {
            LL t = min(i, m - j) + min(m - i, j);
            f[i + j] = (f[i + j] + 1ll * t * C[m][j] % mod * C[m][i] % mod) % mod;
        }
    }   
}
int main() {
    n = read(), m = read();
    for (int i=1; i<n; ++i) {
        int u = read(), v = read(), w = read();
        add_edge(u, v, w);
    }
    init();
    dfs(1, 0);
    cout << Answer;
    return 0;
}