• 最后一场多校，记录一下。。。

• 最近一个月听周的《晴天》听疯了。。单曲循环一千万次- -!

• 这场是朝鲜金策工业大学出的题，感受到了完全不同的画风。。有两点印象深刻

  • 第一，题目描述不拖泥带水，非常清晰，可读性好，题目表述非常简洁。感觉就应该这样啊，，见过太多题目强行加入一个奇怪的故事背景，搞啥？自认为增加了趣味性，其实适得其反。。这一点真是值得学习。
  • 第二，标程写得很棒，想说，这种风格调教出来的代码才是给别人看的好么–

HDU5407 CRB and Candies

• 求 $$LCM\left({n\choose 0},{n\choose 1}\dots {n\choose n}\right)$$
• 令 $$F(n)=LCM\left({n\choose 0},{n\choose 1}\dots {n\choose n}\right)$$ 以及 $$G(n)=LCM\left(1,2,\dots n\right)$$ 则有 $$F(n)={G(n+1)\over {n+1}}$$ 为啥捏？不造哇( ⊙o⊙ )。。。

• 显然$G(1)=1$，考虑$G(n)$的质因数分解形式，知道

  $$G(n) = \begin{cases} G(n-1), & \text{if $n=p^k$} \\[2ex] G(n-1)*p, & \text{if $n!=p^k$} \end{cases}$$ 其中$p$表示一个质数，即判断$n$是否能表达成某个质数的整数$k$次方.

• 最后的除以$n+1$部分需要用逆元处理一下

/* **********************************************

  File Name: 5407.cpp

  Auther: zhengdongjian@tju.edu.cn

  Created Time: 2015年08月21日 星期五 09时06分16秒

*********************************************** */
#include <bits/stdc++.h>
using namespace std;

/*
 * let f(n)=lcm(C(n,0),...,C(n,n)),
 * g(n)=lcm(1,2,...,n).
 * Then f(n)=g(n+1)/(n+1)..
 * g(1)=1,
 * g(n)=g(n-1) if n != p^k, as p is a prime
 *     =g(n-1)*p if n == p^k.
 */

typedef long long ll;
const int MOD = 1000000007;
const int MAX = 1000002;

int g[MAX] = {0};
bool is_prime[MAX];

//return: gcd(a, b).
ll extgcd(ll a, ll b, ll& x, ll& y) {
    ll d = a;
    if (b) {
        d = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    } else {
        x = 1, y = 0;
    }
    return d;
}

ll mod_inverse(ll a, ll mod) {
    ll x, y;
    extgcd(a, mod, x, y);
    return (x % mod + mod) % mod;
}

int main() {
    memset(is_prime, true, sizeof(is_prime));
    for (int i = 2; i <= MAX / i; ++i) {
        for (int j = i * i; j < MAX; j += i) {
            is_prime[j] = false;
        }
    }
    for (int i = 2; i < MAX; ++i) {
        if (is_prime[i]) {
            for (ll j = i; j < MAX; j *= i) {
                g[j] = i;
            }
        }
    }
    g[1] = 1;
    for (int i = 2; i < MAX; ++i) {
        if (g[i]) {
            g[i] = (ll)g[i] * g[i - 1] % MOD;
        } else {
            g[i] = g[i - 1];
        }
    }
    /*
    for (int i = 1; i < 10; ++i) {
        printf("g[%d] = %d\n", i, g[i]);
    }
    */

    int T;
    scanf(" %d", &T);
    while (T--) {
        int x;
        scanf(" %d", &x);
        printf("%d\n", (int)(((ll)g[x + 1] * mod_inverse(x + 1, MOD)) % MOD));
    }
    return 0;
}

HDU5410

• 买东西，拿糖
• 奇怪的背包，题解做了一些分析，然后搞啊搞，先排序什么的。。。
• 然而窝搞啊搞了好久，搞了一个更奇怪的多重背包$dp$。
• 将每种商品拆成$1,2,4,\dots,2^k$组合，这是典型的多重背包做法，但是这个问题的特殊性是，比如在买了$2$件该物品后，再买$4$件该物品，得到的糖不再是$2A_i+B_i$而是$2A_i$。于是对拆完后的所有商品做$dp$。考虑$dp[i][j][0]$表示前$i$件商品，花费$j$，且不拿第$i$件物品最多得到的糖；$dp[i][j][1]$表示…拿了至少$1$件第$i$种物品最多能得到的糖。那么： $$dp[i][j][0] =max \begin{cases} dp[i-1][j][0\ or\ 1], & \text{如果 $i$是原来所属商品分解后的第一件} \\[2ex] dp[i-1][j][0], & \text{如果 $i$不是上述第一件} \end{cases}$$
  $$dp[i][j][1] = max\ of \begin{cases} dp[i-1][j-w[i]][0\ or\ 1]+A_i+B_i, & \text{如果$i$是原来所属商品分解后的第一件 } \\[2ex] dp[i-1][j-w[i]][0]+A_i+B_i, & \text{如果 $i$不是上述第一件}\\[2ex] dp[i-1][j-w[i]][1]+A_i, & \text{同上} \end{cases}$$
• 简单分析一下，原来每件商品至多被拆成$log\ W_i$件，总共至多为$nlog\ {W}_{max}$件，总状态则为$mnlogW_{max}$每次转移为$O(1)$的，第一维空间可以优化掉，于是时间复杂度$O\left(mnlogW_{max}\right)$，空间复杂度$O\left(m\right)$，足够通过本题数据。

/* **********************************************

  File Name: 5.cpp

  Auther: zhengdongjian@tju.edu.cn

  Created Time: 2015年08月20日 星期四 12时32分36秒

*********************************************** */
#include <bits/stdc++.h>
using namespace std;

const int MAX = 1024;
struct Node {
    int w;
    int a;
    int b;
};
vector<Node> V;
vector<int> pre;
int W[MAX], A[MAX], B[MAX];
int dp[MAX << 1][2];
int n, m;

int main() {
    int T;
    scanf(" %d", &T);
    while (T--) {
        scanf(" %d %d", &m, &n);
        V.clear();
        pre.clear();
        V.push_back((struct Node){0, 0});
        pre.push_back(0);

        for (int i = 0; i < n; ++i) {
            scanf(" %d %d %d", W + i, A + i, B + i);
            /* gao */
            Node tp;
            int k = 1;
            int idx = (int)V.size();
            while (k * W[i] <= m) {
                tp.w = k * W[i];
                tp.a = A[i] * k;
                tp.b = B[i];
                //tp.c = A[i] * k + B[i];
                V.push_back(tp);
                pre.push_back(idx);
                k <<= 1;
            }
        }

        memset(dp, 0, sizeof(dp));
        for (int i = 1; i < (int)V.size(); ++i) {
            for (int j = m; j >= 0; --j) {
                //dp[j] = max(dp[j], dp[j - V[i].w] + V[i].c);
                //dp[i][j][0] = ..
                if (i == pre[i]) {
                    dp[j][0] = max(dp[j][0], dp[j][1]);
                    if (j >= V[i].w) {
                        dp[j][1] = max(dp[j][1], max(dp[j - V[i].w][0], dp[j - V[i].w][1]) + V[i].a + V[i].b);
                    }
                } else {
                    if (j >= V[i].w) {
                        dp[j][1] = max(dp[j][1], dp[j - V[i].w][0] + V[i].a + V[i].b);
                        dp[j][1] = max(dp[j][1], dp[j - V[i].w][1] + V[i].a);
                    }
                }
            }
        }
        int ans = max(dp[m][0], dp[m][1]);
        printf("%d\n", ans);
    }
    return 0;
}

HDU5411

• 关系矩阵搞出来求和即可，构造出分块矩阵即可。题解构造出的矩阵为$(n+1)\times (n+1)$我的是$2n\times 2n$，简单优化一下才能通过。。

/* **********************************************

  File Name: 5411.cpp

  Auther: zhengdongjian@tju.edu.cn

  Created Time: 2015年08月20日 星期四 18时11分09秒

*********************************************** */
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MOD = 2015;
const int MAX = 101;
struct Mat {
    int n;
    int a[MAX][MAX];
    Mat(int _n = 0, bool flag = false) {
        n = _n;
        memset(a, 0, sizeof(a));
        if (flag) {
            for (int i = 0; i < n; ++i) {
                a[i][i] = 1;
            }
        }
    }
    Mat operator*(const Mat& b)const {
        Mat res(n);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (a[i][j] == 0) continue;
                for (int k = 0; k < n; ++k) {
                    res.a[i][k] += a[i][j] * b.a[j][k];
                    if (res.a[i][k] >= MOD) {
                        res.a[i][k] %= MOD;
                    }
                }
            }
        }
        return res;
    }
};

Mat fast_pow(Mat a, int m) {
    Mat res(a.n, true);
    while (m) {
        if (m & 1) {
            res = res * a;
        }
        a = a * a;
        m >>= 1;
    }
    return res;
}

int main() {
    int T;
    scanf(" %d", &T);
    while (T--) {
        int n, m;
        scanf(" %d %d", &n, &m);
        Mat res(n << 1);
        for (int i = 1; i <= n; ++i) {
            int k, x;
            scanf(" %d", &k);
            while (k--) {
                scanf(" %d", &x);
                res.a[i - 1][x - 1] = 1;
            }
        }
        for (int i = n; i < (n << 1); ++i) {
            res.a[i - n][i] = 1;
            res.a[i][i] = 1;
        }
        res = fast_pow(res, m);
        /*
        for (int i = 0; i < res.n; ++i) {
            for (int j = 0; j < res.n; ++j) {
                printf("%d ", res.a[i][j]);
            }
            puts("");
        }
        */
        int sum = 1;
        for (int i = 0; i < n; ++i) {
            for (int j = n; j < (n << 1); ++j) {
                sum += res.a[i][j];
            }
        }
        sum %= MOD;
        printf("%d\n", sum);
    }
    return 0;
}

HDU5414

• 仔细分析后，只要满足

  • $|s|\le |t|$
  • $s$能匹配成$t$的子序列
  • 设$t$前$k$个字母连续相同，则$s$前$k$个也必须对应相同

  就可以满足。唯一比较难想的是诸如ale如果添加到apple，似乎需要往$a$后面加$2$个$p$才能得到，但其实可以通过先加一个$p$，然后再向$a$后加$1$个$p$，就可以成功避开题目$c!=d$的限制

 /* **********************************************

  File Name: 5414.cpp

  Auther: zhengdongjian@tju.edu.cn

  Created Time: 2015年08月21日 星期五 10时33分17秒

*********************************************** */
#include <bits/stdc++.h>
using namespace std;

const int MAX = 100007;
char s[MAX], t[MAX];

int main() {
    int T;
    scanf(" %d", &T);
    while (T--) {
        scanf(" %s %s", s, t);
        int len1 = strlen(s), len2 = strlen(t);
        if (len1 > len2 || s[0] != t[0]) {
            puts("No");
            continue;
        }
        char c = t[0];
        int k = 0;
        for (int i = 0; i < len2; ++i) {
            if (t[i] == c) ++k;
            else break;
        }
        for (int i = 0; i < len1; ++i) {
            if (s[i] == c) --k;
            else break;
        }
        if (k > 0) {
            puts("No");
            continue;
        }
        int i = 0, j = 0;
        while (i < len1 && j < len2) {
            s[i] == t[j] ? (++i, ++j) : ++j;
        }
        puts(i == len1 ? "Yes" : "No");
    }
    return 0;
}

HDU5416

• 考虑到异或运算的特殊性质，设$1$为根，对子树中不经过根的路径，不妨假设路径上最高（设若每条边长为1，则此处高度即为到根距离）的一个点为$u$，且路径由$xu$和$uy$两段组成，那么
  $$\begin{align} val(xy) &= val(xu)\oplus val(uy)\\ &= 0\oplus val(ux) \oplus val(uy)\\ &= \left(val(1u)\oplus val(1u)\right)\oplus val(ux) \oplus val(uy)\\ &= val(1x)\oplus val(1y)\end{align}$$ 于是只需要预处理出$1$到各个点的路径异或值即可。统计的时候组合一下即可，另外$f(u,v)$中$u$可以等于$v$，因此当$Query\ 0$时要多注意一下。

/* **********************************************

  File Name: 5416.cpp

  Auther: zhengdongjian@tju.edu.cn

  Created Time: 2015年08月21日 星期五 09时53分14秒

*********************************************** */
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> P;
typedef long long ll;
const int MAX = 100007;
const int MAX_VAL = MAX << 1;

vector<P> G[MAX];
bool vis[MAX];
int cnt[MAX_VAL];

void dfs(int u, int val) {
    vis[u] = true;
    if (u ^ 1) {
        ++cnt[val];
    }

    for (auto it = G[u].begin(); it != G[u].end(); ++it) {
        if (vis[it->first]) continue;
        dfs(it->first, (it->second) ^ val);
    }
}

int main() {
    int T;
    scanf(" %d", &T);
    while (T--) {
        int n, q;
        scanf(" %d", &n);
        for (int i = 1; i <= n; ++i) {
            G[i].clear();
        }
        int u, v, c;
        for (int i = 1; i < n; ++i) {
            scanf(" %d %d %d", &u, &v, &c);
            G[u].push_back(P(v, c));
            G[v].push_back(P(u, c));
        }
        memset(vis, false, sizeof(vis));
        memset(cnt, 0, sizeof(cnt));
        dfs(1, 0);

        scanf(" %d", &q);
        while (q--) {
            scanf(" %d", &c);
            ll ans = 0LL;
            if (c == 0) {
                ans += n + cnt[0];
                for (int i = 0; i < MAX_VAL; ++i) {
                    ans += (ll)cnt[i] * (cnt[i] - 1) / 2;
                }
            } else {
                for (int i = 0; i < MAX_VAL; ++i) {
                    ans += (ll)cnt[i] * (cnt[i ^ c]);
                }
                ans >>= 1;
                ans += cnt[c];
            }
#ifdef ONLINE_JUDGE
#define lld I64d
#endif
            printf("%lld\n", ans);
        }
    }
    return 0;
}