染色相关
染色问题是一类NPC问题。
它的一般形式是给定一个无向联通图(G_{<n,m>})，要求用(k)种颜色对其染色。使得每一条边所连的两个端点不同色。
这一类问题通常需要很高的时间复杂度。但在特殊的图中，这一类问题能得到很优秀的解法。
例1 jzoj6079
Problem
给定无向联通图(G_{<n,m>})，要求(k)染色的方案数
(nle 10^5, mle n+5, kle 10^5)
Solution
很经典的一道题目。
首先注意到，(mle n + 5)这个有用的性质。
再观察一下(k)染色图的一些性质。
注意到，度数为(1)的点是可以直接缩掉的。
然后转化一下，把一条边看做两个边权组成，一个边权表示两个点颜色相同时的方案，另一个则表示两个点颜色不同时的方案，显然一开始边权的组成是((0,1))。
然后考虑缩一下度数为(2)的点。
事实上是可以通过推式子得出的。然后会发现缩完之后最终图的大小是(nle 10,mle15)的。
于是直接搜索就好了。
例2 jzoj
Problem
给定(m)条原始边，并按照以下规则加边，得到的最终图求(n)染色方案。
若(alt blt c)，且((a,b),(a,c))有边，则连((a,c))
(n,mle 1e6)
Solution
观察到这道题连边的特殊性质。
可以发现，如果按节点编号从大到小染色，假设一个点的度数为最终图里连向多少条比它编号大的点，那么答案很显然就是(prod_i n-度数_i)。
因为比它大的点颜色都互不相同！
现在关键就变成了求最终图里每个点的度数。
然后发现一个很重要的性质：
如果最终图里两个点(x,y)有边，则必然可以在原图中找到一条路径，使得这个路径上点的编号都小于(min(x,y)).
于是就可以从小到大去构图，每次维护好图的连通性，每次当前点所在联通块有多少个相邻点就是当前点的度数了。
这个可以用启发式合并或者线段树合并。事实上启发式合并由于有set，map这种高级骚操作，所以时间复杂度虽然是两个(log)的，但依然跑的比线段树的一个(log)快。
容斥相关
计数题一般有容斥，这是计数题的一大特点。
例3 jzoj3170
Problem
给定(n)个箱子，每个箱子里有若干种玩具，玩具编号从(1sim m)，然后让你求有多少种选择箱子的方案，使得每种玩具都至少有一个。
(nle 10^6, mle 20)
Solution
首先，要求至少，那肯定一波容斥了。转化为求一个都没有的方案。
然后必然是要枚举哪些至少没有，第二次容斥。
那么问题现在就转化为了，(n)个箱子中选哪些箱子，不包括给定集合。
然后考虑它的对应问题，(n)个箱子中选哪些箱子，被给定集合包括，这里的包括显然指的是真子集。
然后这个有个经典做法是分治。考虑把(m)位从高位到低位处理。然后考虑当前这一位的贡献，可以由(f_i ightarrow f_{i+mid})。
我们来考虑这样做法的正确性。
由于最终计数的(f_i)表示的是(i)的所有子集中包含了多少个箱子，换句话说，这些箱子的并集(in i)。由于我们依次考虑了(i)的某一位是否为(1)时的贡献，且当某一位为(0)时，我们不会累加为(1)的答案。换句话说，只有当某一位为(1)时，我们会累加(0,1)的答案，所以可以累加出最终答案。
Code
#include <bits/stdc++.h>
#define F(i, a, b) for (int i = a; i <= b; i ++)
const int T = 1e6 + 10, Mo = 1e9 + 7, S = 2e6;
using namespace std;
int n, m, tot, x, sum, N, ans;
int shl[T], f[S];
void CDQ(int l, int r) {
if (l >= r) return;
int m = l + r >> 1;
CDQ(l, m), CDQ(m + 1, r);
F(i, l, m)
f[m + i - l + 1] += f[i];
}
int main() {
scanf("%d%d", &n, &m), shl[0] = 1;
F(i, 1, max(n, m)) shl[i] = (shl[i - 1] * 2LL) % Mo;
N = shl[m] - 1;
F(i, 1, n) {
scanf("%d", &tot), sum = 0;
F(j, 1, tot)
scanf("%d", &x), sum += shl[x - 1];
f[sum] ++;
}
CDQ(0, N);
F(i, 0, N) {
int tot = 0;
for (int x = i; x; x -= x & (- x), tot ++);
if (tot & 1) ans = (ans - (shl[f[N - i]] - 1)) % Mo; else ans = (ans + (shl[f[N - i]] - 1)) % Mo;
}
printf("%d
", (ans + Mo) % Mo);
}
例4 jzoj5664
Problem
- (Mx,My,Tx,Tyle 800,Kle 50,Rle 1600)
Solution
还是很经典的一道题目。
首先必然要考虑容斥了，因为有些向量不能走。令(s_k)表示走了至少(k)次不合法向量的方案数，那么答案可以写成$$Ans=sum_{i=0}r(-1)is_i$$
考虑如何求(S_i)，这个是很经典的。
容易想到令(g_{i,x})表示只走不合法向量，到达((10x,10x))的方案数。
(f_{i,x,y})表示(i)步，任意向量，到达((x,y))的方案数。
那么就有$$s(k)=sum_{i=0}^{min(frac{T_x}{10},frac{T_y}{10})}inom{r}{k}g[k][i]f[r-k][T_x-10i][T_y-10i]$$
然后现在就把问题变为求(f_{i,x,y})了。
这里有一个很经典的套路就是 降维。
考虑(Fx_{i,j},Fy_{i,j})分别表示走(i)步，到(x)轴的第(j)个点， (y)轴的第(j)个点的方案。
那么就有(f_{i,x,y}=Fx_{i,x}*Fy_{i,y})。这个是很容易证明的。
而求(Fx,Fy)则可以很快求出。
所以时间复杂度很优秀。
注意边界。
Code
#include <iostream>
#include <cstring>
#include <cstdio>
#define F(i, a, b) for (int i = (a); i <= (b); i ++)
#define G(i, a, b) for (int i = (a); i >= (b); i --)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define add(a, b) ((a) = (a + b) % Mo)
const int Mo = 1e4 + 7;
const int R = 1601, N = 801, T = 51;
using namespace std;
int Answer, Tx, Ty, Mx, My, r, m, Limit, c[R][R];
int g[R][N / 10], k[T], Fx[R][N], Fy[R][N], Sx[R][N], Sy[R][N];
int S(int k) {
int ans = 0;
F(i, 0, Limit)
add(ans, 1ll * c[r][k] % Mo * g[k][i] * Fx[r - k][Tx - 10 * i] * Fy[r - k][Ty - 10 * i] % Mo);
return ans;
}
int ksm(int x, int y) {
int ans = 1;
for (; y ; y >>= 1, x = (1ll * x * x) % Mo)
if (y & 1)
ans = (1ll * ans * x) % Mo;
return ans;
}
int main() {
freopen("jump.in", "r", stdin);
freopen("jump.out", "w", stdout);
scanf("%d%d%d%d%d%d", &Tx, &Ty, &Mx, &My, &r, &m);
F(i, 1, m) scanf("%d", &k[i]), k[i] /= 10;
Limit = min(Tx / 10, Ty / 10), g[0][0] = 1;
F(i, 0, r - 1)
F(j, 0, Limit)
if (g[i][j])
F(p, 0, m)
if (j + k[p] <= Limit)
add(g[i + 1][j + k[p]], g[i][j]);
Fx[0][0] = 1;
F(j, 0, Tx) Sx[0][j] = 1;
F(i, 1, r) F(j, 0, Tx) {
if (j - Mx <= 0)
Fx[i][j] = Sx[i - 1][j];
else
Fx[i][j] = Sx[i - 1][j] - Sx[i - 1][j - Mx - 1];
if (j) Sx[i][j] = Sx[i][j - 1];
add(Sx[i][j], Fx[i][j]);
}
Fy[0][0] = 1;
F(j, 0, Ty) Sy[0][j] = 1;
F(i, 1, r) F(j, 0, Ty) {
if (j - My <= 0)
Fy[i][j] = Sy[i - 1][j];
else
Fy[i][j] = Sy[i - 1][j] - Sy[i - 1][j - My - 1];
if (j) Sy[i][j] = Sy[i][j - 1];
add(Sy[i][j], Fy[i][j]);
}
F(i, 0, r) c[i][0] = 1;
F(i, 1, r)
F(j, 1, r)
c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % Mo;
F(i, 0, r)
add(Answer, ((i & 1) ? ( - 1) : ( 1 )) * S(i));
printf("%d
", (Answer + Mo) %Mo);
}