主要思路
首先规定，\(N<M\)。之后写出统计答案的式子：
\[ \sum_{i=1}^N \sum_{j=1}^M lcm(i,j) \\ \sum_{i=1}^N \sum_{j=1}^M \frac{ij}{\gcd(i,j)} \]
然后我们可以试着去枚举最大公约数\(gcd(i,j)=d\)，然后让\(i,j\)成为唯一的两个互质因子。
P3327:「SDOI2015」约数个数和题解
主要思路和推导
这道题还是比较有意思的（啊呀看了好久的题解才会写，真菜），主要就是把\(d\)转换成了：
\[ d(xy) = \sum_{i|x}^x \sum_{j|y}^y [\gcd(i,j) = 1] \]
可以感性理解一下：每一次约数被枚举出来的时候，只有互质的情况下才会被计数，避免了重复计数。 Continue reading →
P2257:YY 的 GCD 题解
LibreOJ 6005:「网络流 24 题」最长递增子序列题解
主要思路
这道题还是很有意思的，建图方式非常的巧妙。首先我们先把第一问的 DP 用 \(O(n \log n)\) 的时间求解一下，顺便搞到一个数组\(f[i]\)，含义是以\(i\)为结尾的最长子序列长度。建图的时候要注意的是，每一个位置对应的点要拆成两个：这是为了保持答案的唯一性。所以对于\(f[i]=1\)的点\(i\)，连边\((s,i)\)；对于\(f[i]=k\)的点\(i\)，连边\((i+n,t)\)。之后，如果对于\((u,v), f[v] = f[u] + 1, arr[u] \leq arr[v]\)进行连边，跑个最大流就可以出答案了。
第三问其实跟第二问的差不多，只需要把点\(1\)和点\(n\)的外向边（到源点或者是汇点的边）的最大流限制改成无穷大即可。
「Fortuna OJ」Mar 8th – Group A 解题报告
春季集训的最后一天了，果然比赛也崩了。
A – 涂色游戏
这道题怎么这么神仙啊。
我们先来考虑一行内的方案数。我们可以设出状态：\(f[i][j]\)代表前\(i\)个元素中有\(j\)种颜色，式子很好推：
\[ f[i][j] = f[i-1][j-1]*(p-(j-1))+f[i-1][j]*j \]
因为列数是固定的，所以我们只要保留当\(i=m\)的值即可，所以我们设\(g[i]=f[m][i]\)，也就是单行有\(i\)种颜色的方案。之后我们考虑设计一个状态来求我们的答案：我们可以固定一行，然后讨论两行放在一起的情况。所以，\(dp[i][k]\)的意义是前\(i\)行的方案，其中最后一行包括了\(k\)种颜色。
\[ dp[i][k] = dp[i-1][j]+\frac{g[k]}{{ p \choose k }}*\sum_{ x = max\{ j,k,q \} }^{ min\{ p,j+k \} } { { j \choose j+k-x }*{ p-j \choose x-j } } \]
我知道这个式子很复杂，我们来解释一下。首先，状态\(dp[i][k]\)代表到了第\(i\)行，第\(i\)行有\(k\)种颜色，枚举上一行有\(j\)种颜色，所以从\(dp[i-1][j]\)转移过来。因为我们这里单独枚举颜色类型对答案的贡献，所以我们要消去\(g[i]\)中答案种类对\(g[i]\)的影响，避免算重。之后再枚举两行一共有\(x\)种颜色，因为\(j\)和\(k\)可能会有重复，所以我们需要单独枚举，这个\(x\)的上下界为：\( [max\{ j,k,q \},min\{ p, j+k \}] \)。之后就是喜闻乐见的两部分的单独枚举：\( { j \choose j+k-x } \)代表枚举两行共有的部分，\( { p-j \choose x-j } \)则是代表两行不共有的部分。所以，这样就可以把答案统计出来了。
然后这道题的\(f[i]\)可以用矩阵快速幂来搞，复杂度进一步降低。
POJ1741:Tree 题解
主要思路
这道题应该算是点分治的一道经典题目。点分治的精髓就在于找到重心、对子树进行计算并且合并答案，之后删除中心变成子树内的小问题，分治思想非常的巧妙。
我们首先写好找根函数：
// root finding functions;
void dfs1(int u, int fa, int siz)
{
son[u] = 1;
int res = 0;
for (int i = head[u]; i != -1; i = edges[i].nxt)
{
if (edges[i].to == fa || done[edges[i].to])
continue;
dfs1(edges[i].to, u, siz);
son[u] += son[edges[i].to];
res = max(res, son[edges[i].to] - 1);
}
res = max(res, siz - son[u]);
if (res < rootKey)
root = u, rootKey = res;
}
void findRoot(int src, int siz)
{
root = src, rootKey = siz;
dfs1(src, 0, siz);
}
遍历子树：我们设定一个\(dist[]\)数组，算出距离的答案，并且无视曾经被当作根的节点，并向cnt[from[u]]进行自增操作，维护子树的大小，并把本身编号加入vec供之后进行排序用途。
// the calc one;
void dfs(int u, int fa)
{
vec.push_back(u);
for (int i = head[u]; i != -1; i = edges[i].nxt)
if (edges[i].to != fa && !done[edges[i].to])
{
cnt[from[u]]++;
dist[edges[i].to] = dist[u] + edges[i].weight;
from[edges[i].to] = from[u];
dfs(edges[i].to, u);
}
}
点分治：我们在计算完子树答案之后，合并的方法是主要的问题。我们可以考虑将vec进行排序，然后通过递增的性质设置首尾指针，并且去除掉当前子树内的错误答案（因为子树内部的路径不经过根，所以要去掉，之后的分治子问题中会处理这些内部路径）。
void pdq(int curt, int siz)
{
memset(son, 0, sizeof(son));
memset(cnt, 0, sizeof(cnt));
findRoot(curt, siz);
dist[root] = 0, done[root] = true;
vec.clear(), vec.push_back(root), from[root] = root;
cnt[root]++;
for (int i = head[root]; i != -1; i = edges[i].nxt)
if (!done[edges[i].to])
{
from[edges[i].to] = edges[i].to, cnt[edges[i].to]++;
dist[edges[i].to] = edges[i].weight;
dfs(edges[i].to, root);
}
sort(vec.begin(), vec.end(), compare);
cnt[from[vec[0]]]--;
int l = 0, r = vec.size() - 1;
while (l < r)
{
while (dist[vec[l]] + dist[vec[r]] > k)
cnt[from[vec[r--]]]--;
answer += r - l - cnt[from[vec[l]]];
cnt[from[vec[++l]]]--;
}
int pos = root;
for (int i = head[pos]; i != -1; i = edges[i].nxt)
if (!done[edges[i].to])
pdq(edges[i].to, son[edges[i].to]);
}
嗯，写完了。具体代码如下：
代码
// POJ1741.cpp
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
const int MAX_N = 10100, INF = 0x3f3f3f3f;
int head[MAX_N], current, k, n, tmpx, tmpy, tmpz, root, rootKey, son[MAX_N];
int from[MAX_N], dist[MAX_N], cnt[MAX_N];
bool done[MAX_N];
long long answer = 0;
vector<int> vec;
struct edge
{
int to, nxt, weight;
} edges[MAX_N << 1];
bool compare(int a, int b) { return dist[a] < dist[b]; }
void addpath(int src, int dst, int weight)
{
edges[current].to = dst, edges[current].nxt = head[src];
edges[current].weight = weight, head[src] = current++;
}
// root finding functions;
void dfs1(int u, int fa, int siz)
{
son[u] = 1;
int res = 0;
for (int i = head[u]; i != -1; i = edges[i].nxt)
{
if (edges[i].to == fa || done[edges[i].to])
continue;
dfs1(edges[i].to, u, siz);
son[u] += son[edges[i].to];
res = max(res, son[edges[i].to] - 1);
}
res = max(res, siz - son[u]);
if (res < rootKey)
root = u, rootKey = res;
}
void findRoot(int src, int siz)
{
root = src, rootKey = siz;
dfs1(src, 0, siz);
}
// the calc one;
void dfs(int u, int fa)
{
vec.push_back(u);
for (int i = head[u]; i != -1; i = edges[i].nxt)
if (edges[i].to != fa && !done[edges[i].to])
{
cnt[from[u]]++;
dist[edges[i].to] = dist[u] + edges[i].weight;
from[edges[i].to] = from[u];
dfs(edges[i].to, u);
}
}
void pdq(int curt, int siz)
{
memset(son, 0, sizeof(son));
memset(cnt, 0, sizeof(cnt));
findRoot(curt, siz);
dist[root] = 0, done[root] = true;
vec.clear(), vec.push_back(root), from[root] = root;
cnt[root]++;
for (int i = head[root]; i != -1; i = edges[i].nxt)
if (!done[edges[i].to])
{
from[edges[i].to] = edges[i].to, cnt[edges[i].to]++;
dist[edges[i].to] = edges[i].weight;
dfs(edges[i].to, root);
}
sort(vec.begin(), vec.end(), compare);
cnt[from[vec[0]]]--;
int l = 0, r = vec.size() - 1;
while (l < r)
{
while (dist[vec[l]] + dist[vec[r]] > k)
cnt[from[vec[r--]]]--;
answer += r - l - cnt[from[vec[l]]];
cnt[from[vec[++l]]]--;
}
int pos = root;
for (int i = head[pos]; i != -1; i = edges[i].nxt)
if (!done[edges[i].to])
pdq(edges[i].to, son[edges[i].to]);
}
int main()
{
while (scanf("%d%d", &n, &k) && n != 0)
{
answer = 0;
memset(head, -1, sizeof(head)), current = 0;
for (int i = 1; i <= n - 1; i++)
scanf("%d%d%d", &tmpx, &tmpy, &tmpz), addpath(tmpx, tmpy, tmpz), addpath(tmpy, tmpx, tmpz);
memset(done, false, sizeof(done));
pdq(1, n);
printf("%lld\n", answer);
}
return 0;
}