今天讲了不少有趣题，但是可惜很多题没有提交入口，不牛。
先放个课件吧。 度盘
Codechef - Cycles And Colorings 加强
给出一张 \(n\) 个点 \(m\) 条边的无向连通简单图，你需要完成以下两个任务的其中一个，输出方案。
- 给出一个三染色方案。
- 找一个奇环，使得删去它后图仍连通。（注意：这里只删边）
\(n\le 10^5,m\le 2\times 10^5\) 。
原题：四染色
首先找一棵生成树，然后把树上的边删掉。如果剩下有奇环直接做完了。否则可以得到两个二分图，一个二分图有两种颜色，合起来就是四种颜色。然后原题就做完了。
事实上，我们能做的更好。考虑这样找生成树：
- 把 \(1\) 染成黑色，然后从 \(1\) 开始 DFS 。
- 假如当前 DFS 到的点 \(u\) 是黑色，那么就先把 \(u\) 的所有没有颜色的邻居染成白色，然后依次 DFS 每个被 \(u\) 染的点。
- 否则 \(u\) 是白色，那么依次染黑每个没有颜色的邻居，并在染黑一个点后立刻 DFS 这个点。
注意这两者的区别：一个是先染所有邻居再 DFS ，一个是边染边 DFS 。
这样做的好处是不会有两个黑点相邻，那么最后黑点就只用一种颜色。
时间复杂度 \(O(n+m)\) 。
AGC001E BBQ Hard 加强
有 \(n\) 个数对 \((a_i, b_i)\)，求出
\[\sum_{i=1}^{n}\sum_{j=i + 1}^{n}\binom{a_i+b_i+a_j+b_j}{a_i+a_j} \]\(n\le2\times10^5,\sum_{i}(a_i+b_i)=m\le 2\times 10^7\) 。
原题：\(a_i,b_i\le2\times10^3\) 。
首先可以得到这个式子的一个含义：从 \((-a_i,-b_i)\) 走到 \((a_j,b_j)\) ，每次向上或向右走，求方案数。由此不难得到原题做法。
题目限制是若干数加起来 \(\le 2\times 10^7\) ，那么不难想到根号分治。小对小、大对大直接暴力，小对大可以注意到一定会经过 \(x+y=0\) 这条直线，先从小块走到直线上再走到大块，这样直线上只有 \(O(\sqrt m)\) 个点被经过，那么暴力即可。复杂度 \(O(m)\) 。
上面那个没看懂也没关系，我们有个更巧妙的方法。注意到
\[\binom{a_i+b_i+a_j+b_j}{a_i+a_j}=\sum_x\binom{a_i+b_i}{a_i+x}\binom{a_j+b_j}{a_j+x} \]那么答案等于
\[\begin{align} \sum_{i}\sum_j\binom{a_i+b_i+a_j+b_j}{a_i+a_j}=&\sum_{i}\sum_j\sum_x\binom{a_i+b_i}{a_i+x}\binom{a_j+b_j}{a_j-x} \\=&\sum_x\sum_{i}\sum_j\binom{a_i+b_i}{a_i+x}\binom{a_j+b_j}{a_j-x} \\=&\sum_x(\sum_{i}\binom{a_i+b_i}{a_i+x})(\sum_j\binom{a_j+b_j}{a_j-x}) \end{align} \]考虑一个 \(x\) ，左边组合数有值的充要条件是 \(x\in[-a_i,b_i]\) ，也就是说，对于一个 \(i\) ，对左边求和有贡献的 \(x\) 只有 \(O(a_i+b_i)\) 个，右边显然是一样的，那么暴力计算上面那个式子即可。
草不想写了，看课件去吧
完结撒花！
没绷住，怎么只写了最简单的两个题
感觉全错了啊，下次还是给有难度的题单独写个题解好了