唐老师的博客[n<=100可做]

歪果仁的超强PPT，看完之后你就知道怎么做[nm<=500的情况]（只要你忽略证明）

搜FKT，完美匹配计数统统搜不到。

只有搜51nod1034 v3。。。

或是 Counting perfect matchings in planar graphs

才搜的到。

这个在国内也太冷了吧。

我来用中文复述一遍PPT内容：

1.1*2骨牌铺格子可以转化为求完美匹配数$Perfertmatch$。

2.定义排列M,让M中第$2i$个和第$2i+1$个匹配。

发现$Perfectmatch = \sum_{M}\prod A_{2i,2i+1}$

$A_{i,j}=1$当且仅当$i,j$间有边。

3.这个形式让我们想到了行列式，结合矩阵树定理的经验开始往行列式靠。

然后发现按$M$的逆序对数为奇数乘一个$-1$否则不乘后得到的：

$Pfaffian = \sum_{M}sgn(M)\prod A_{2i,2i+1}$

$sgn(M)$即为-1或1。

如果$A$满足$\forall i,j\ A_{i,j} = -A_{j,i}$

有：

$Pfaffian^2 = det(A)$

然后如果还有$|Pfaffian| = Perfectmatch$

4.明显如果我们把边变成有向边就可以满足$\forall i,j\ A_{i,j} = -A_{j,i}$

考虑何时$|Pfaffian| = Perfectmatch$

用一下平面图的性质。

找到内部不包含点的环，保证环上有奇数条顺时针的边。

那么两个相交的环，相交部分对于一个环是顺时针，对于另一个就是逆时针。

合并成的大环也是有奇数条顺时针的边。

然后就莫名其妙证明每个环有奇数条顺时针的边安排可以保证$|Pfaffian| = Perfectmatch$。

那么只要找到安排的方法即可。

5.在原图找一颗生成树，所有边朝叶子方向，然后对于对偶图，找没有在生成树上出现的边，边两边的点连边。（好像不用打点定位的对偶图也就七八十来行吧）

可以证明这是一棵树，然后从叶子开始往上操作，给每个点到父亲的边定向使得这个点所代表的平面区域环中有奇数条顺时针的边。

然后对于这个邻接矩阵求det再开方就行了。
6.骨牌覆盖的图可以把$A$变成$n*n$的，看唐老师博客吧，博主不行了。。。。。。
考虑一个 $n$ 行 $m$ 列的网格图，我们需要用 $1∗2$ 的骨牌将其覆盖。

网格图的内部有一些凸起的边界，骨牌无法平稳的放置在凸起上，因此有些放置骨牌的方法是不可行的。

考虑如下的网格图，红色的边界表示有凸起的边界。蓝色的线表示骨牌，这也是这个图唯一的合法方案。

现在某人想要从所有合法方案中选出两个合法方案组成一对合法方案（可以相同）$A,B$ 和 $B,A$算两个不同的方案对。他想要知道有多少方案对？

输入格式

第一行两个整数 $n,m$ 表示网格图的大小。

接下来 $n$ 行，每行 $m−1$ 个 $0/1$，第 $i$ 行第 $j$ 个变量表示第 $i$ 行的第 $j$ 个格子和 $j+1$个格子中间是否有凸起的边界，$1$ 表示有。

接下来 $n−1$ 行，每行 $m$ 个 $0/1$，第 $i$ 行第 $j$ 个变量表示第 $i$ 行和第 $i+1$ 行的第 $j$ 个格子中间是否有凸起的边界，表示方法同前。

输出格式

输出一行一个整数，表示答案，答案对 $998244353$ 取模。

给个代码（不是我打的）：

#include <bits/stdc++.h>
#define EB emplace_back

typedef long long ll;
typedef std::vector <int> vector;
const int N = 5000, M = 66666, mod = 998244353;

struct edge {
	int u, v;
	edge (int u0 = 0, int v0 = 0) : u(u0), v(v0) {}
} e[M];

int R, C, V, E = 0;
int p[N], mat[N][N], elim[N];
int to[M], first[N], next[M];
int orient[M];

inline void addedge(int u, int v) {
//	fprintf(stderr, "addedge %d %d\n", u, v);
	e[++E] = edge(u, v), next[E] = first[u], first[u] = E;
	e[++E] = edge(v, u), next[E] = first[v], first[v] = E;
}

inline int join(int r, int c) {return (r - 1) * C + 1;}
inline void split(int id, int &r, int &c) {r = --id / C + 1, c = id % C + 1;}
inline int ancestor(int x) {return p[x] == x ? x : (p[x] = ancestor(p[x]));}
inline bool Union(int x, int y) {
	if ((x = ancestor(x)) == (y = ancestor(y))) return true;
	return p[x] = y, false;
}

ll PowerMod(ll a, int n, ll c = 1) {for (; n; n >>= 1, a = a * a % mod) if (n & 1) c = c * a % mod; return c;}

int gauss(int n) {
	int i, j, k, *t, det = 1, cnt; ll coe;
	static int *m[N];
	for (i = 0; i < n; ++i) m[i] = mat[i];
	for (i = 0; i < n; ++i) {
		for (j = i; j < n && !m[j][i]; ++j);
		if (j == n) return 0;
		if (i != j) det = mod - det, std::swap(m[i], m[j]);
		det = (ll)det * m[i][i] % mod;
		coe = PowerMod(m[i][i], mod - 2);
		for (j = 0; j < n; ++j) m[i][j] = m[i][j] * coe % mod;
		for (cnt = 0, k = i; k < n; ++k) if (m[i][k]) elim[cnt++] = k;
		for (k = i + 1; k < n; ++k) if (m[k][i]) {
			coe = mod - m[k][i];
			for (t = elim; t != elim + cnt; ++t)
				m[k][*t] = (m[k][*t] + coe * m[i][*t]) % mod;
		}
	}
	return det;
}

namespace Planar {
	#define ad(x) (((x - 1) ^ 1) + 1)
	int F = 0;
	int belF[M], remain[M], que[M];
	vector face[M];

	inline bool judge(int A, int B, int C, int D) {
		if (B == A + ::C) return (D - 1) % ::C < (C - 1) % ::C;
		if (B == A - ::C) return (C - 1) % ::C < (D - 1) % ::C;
		if (B == A + 1) return C < D;
		if (B == A - 1) return D < C;
		abort();
	}

	void dfs(int i) {
		int j, x = e[i].u, y = e[i].v, z, bestV = 0, bestE = 0;
//		fprintf(stderr, "search face #%d edge #%d (%d, %d)\n", F, i, x, y);
		belF[i] = F, face[F].EB(i);
		for (j = first[y]; j; j = next[j]) {
			if ((z = e[j].v) == x) continue;
			if (!bestV || judge(x, y, z, bestV)) bestV = z, bestE = j;
		}
		if (!bestE) {
			for (j = first[y]; j; j = next[j]) if (e[j].v == x) break;
			bestV = x, bestE = j;
		}
		if (belF[bestE] != F) dfs(bestE);
	}

	int main() {
		int i, f, h, t = 0; bool o;
		for (i = 1; i <= E; ++i)
			if (!belF[i]) ++F, dfs(i), remain[F] = face[F].size();
		for (i = 1; i <= F; ++i)
			for (int e : face[i])
				if (orient[e] && --remain[i] == 1) que[t++] = i;
		for (h = 0; h < t; ++h) {
			f = que[h], o = true;
			if (!remain[f]) continue;
			for (int e : face[f])
				if (orient[e]) o ^= orient[e] != e;
				else i = e;
			orient[ad(i)] = orient[i] = (o ? ad(i) : i);
			if (--remain[ f = belF[ad(i)] ] == 1) que[t++] = f;
		}
		for (i = 1; i <= E; ++i) assert(orient[i]);
		return 0;
	}
}

int main() {
	int i, j, v, n;
	scanf("%d%d", &R, &C), V = R * C;
	if (R & C & 1) return putchar(48), putchar(10), 0;
	for (n = i = 1; i <= R; ++i, ++n)
		for (j = 1; j < C; ++j, ++n)
			if (scanf("%d", &v), !v) addedge(n, n + 1);
	for (n = i = 1; i < R; ++i)
		for (j = 1; j <= C; ++j, ++n)
			if (scanf("%d", &v), !v) addedge(n, n + C);
	std::iota(p + 1, p + (V + 1), 1);
	for (i = 1; i <= E; i += 2)
		if (!Union(e[i].u, e[i].v)) {
			orient[i] = orient[i + 1] = i;
//			fprintf(stderr, "connect %d %d\n", e[i].u, e[i].v);
		}
	Planar::main();
	for (i = 1; i <= E; ++i) if (orient[i] == i)
		mat[e[i].u - 1][e[i].v - 1] = 1, mat[e[i].v - 1][e[i].u - 1] = mod - 1;
	printf("%d\n", gauss(V));
	return 0;
}

	

第二讲　向量运算与复数运算、算法、推理与证明
高考考点
考点解读
平面向量的
运算及运用
1.以平面图形为载体，借助向量考查数量关系与位置关系、向量的线性运算及几何意义
2．以平面向量基本定理为出发点，与向量的坐标运算、数量积交汇命题
3．直接利用数量积运算公式进行运算，求向量的夹角、模或判断向量的垂直关系
复数的概念及运算
1.复数的概念、纯虚数、复数相等、共轭复数等
2．复数的几何意义及四则运算，重点考查复数的乘除运算
程序框图
1.主要考查程序框图的应用及基本算法语句，尤其是含循环结构的程序框图
2．与分段函数的求值、数列求和或求积、统计等有规律的重复计算问题放在一起综合考查
合情推理
1.主要考查合情推理和演绎推理，重点考查归纳推理和类比推理
2．以数表、数阵、图形等为背景与数列、周期性等数学知识相结合考查归纳推理
备考策略
本部分内容在备考时应注意以下几个方面：
(1)加强对向量加法、减法的平行四边形法则与三角形法则的理解、掌握两向量共线与垂直的条件，熟记平面向量的相关公式，掌握求模、夹角的方法．
(2)掌握复数的基本概念及运算法则，在备考时注意将复数化为代数形式再进行求解，同时注意“分母实数化”的运用．
(3)关注程序框图和基本算法语句的应用与判别，尤其是含循环结构的程序框图要高度重视．
(4)掌握各种推理的特点和推理过程，同时要区分不同的推理形式，对归纳推理要做到归纳到位、准确；对类比推理要找到事物的相同点，做到类比合，对演绎推理要做到过程严密．
预测2019年命题热点为：
(1)利用平面向理的基本运算解决数量积、夹角、模或垂直、共线等问题，与三角函数、解析几何交汇命题．
(2)单独考查复数的四则运算，与复数的相关概念、复数的几何意义等相互交汇考查．
(3)程序框图主要是以循环结构为主的计算、输出、程序框图的补全，与函数求值、方程求解、不等式求解数列求和、统计量的计算等交汇在一起命题．
(4)推理问题考查归纳推理和类比推理，主要与数列、立体几何、解析几何等结合在一起命题．
知识整合
1．重要公式
(1)两个非零向量平行、垂直的充要条件
若a＝(x1，y1)，b＝(x2，y2)，则
①a∥b⇔a＝λb(b≠0，λ∈R)⇔x1y2－x2y1＝0.
②a⊥b⇔a·b＝0⇔x1x2＋y1y2＝0.
(2)复数的四则运算法则
(a＋bi)±(c＋di)＝(a±c)＋(b±d)i(a，b，c，d∈R)．
(a＋bi)(c＋di)＝(ac－bd)＋(bc＋ad)i(a，b，c，d∈R)．
(a＋bi)÷(c＋di)＝c2＋d2ac＋bd＋c2＋d2bc－adi(a，b，c，d∈R，c＋di≠0)．
2．重要性质及结论
(1)若a与b不共线，且λa＋μb＝0，则λ＝μ＝0.
(2)已知→OA＝λ→OB＋μ→OC(λ，μ为常数)，则A，B，C三点共线的充要条件是λ＋μ＝1..
(3)平面向量的三个性质
①若a＝(x，y)，则|a|＝＝.
②若A(x1，y1)，B(x2，y2)，则|→AB|＝.
③设θ为a与b(a≠0，b≠0)的夹角，且a＝(x1，y1)，b＝(x2，y2)，则cosθ＝|a||b|a·b＝22.
(4)复数运算中常用的结论：
①(1±i)2＝±2i；②1－i1＋i＝i；③1＋i1－i＝－i；④－b＋ai＝i(a＋bi)；⑤i4n＝1，i4n＋1＝i，i4n＋2＝－1，i4n＋3＝－i，其中n∈N*
3．推理与证明
(1)归纳推理的思维过程
实验、观察→概况、推广→猜测一般结论
(2)类比推理的思维过程
实验、观察→联想、类推→猜测新的结论
(3)(理)数学归纳法证题的步骤
①(归纳奠基)证明当n取第一个值n＝n0(n0∈N*)时，命题成立；
②(归纳递推)假设n＝k(k≥n0，k∈N*)时命题成立，证明当n＝k＋1时，命题也成立．
只要完成了这两个步骤，就可以断定命题对于任何n≥n0的正整数都成立．
Y易错警示i cuo jing shi 
1．忽略复数的定义：
在解决与复数概念有关的问题时，在运用复数的概念时忽略某一条件而致误．
2．不能准确把握循环次数
解答循环结构的程序框图(流程图)问题，要注意循环次数，防止多一次或少一次的错误．
3．忽略特殊情况：两个向量夹角为锐角与向量的数量积大于0不等价；两个向量夹角为钝角与向量的数量积小于0不等价．

问
怎么证明圆锥曲线的光学特性，最好有不用到求导的方法？
答
椭圆
由椭圆的定义——平面上，到定点 
 与 
 距离之和为定值 
 的点的轨迹，这个定义蕴含着一个很显然的事实：
当 
 在椭圆外时，有 
 ；
当 
 在椭圆上时，有 
；
当 
 在椭圆内时，有 
.
见上图，过椭圆上一点 
 的切线，除 
 点外切线上任意一点 
 都在椭圆外（凸性），于是由上面的观察得到：
所以 
 点是切线上到定点 
 与 
 距离之和最小点，故 
 点是反射点。
抛物线
在理解椭圆光学性质的基础上，我们先固定一个焦点 
 ，然后将另一个焦点 
 牵引到无穷远处，离心率
即椭圆最终变为抛物线，而此时反射光 
 的极限位置平行于椭圆长轴。
[1]
双曲线
类似于椭圆的分析，不过我们要熟悉一个结论：
引理
如上图 
 ，选取直线 
 上的动点 
 ，使得 
 最大，当且仅当 
 平分 
 .
证
在 
 上取 
 点关于直线 
 的对称点 
 ，于是
只需证明当取直线上其他点 
 时，总有
即可完成证明
连接 
 ，由 
 得
而在 
 中，由两边只差小于第三边立即可得
有了这个引理，那么接下来的分析顺理成章
见上图，
 是双曲线过 
 点的切线. 我们定义函数 
 ，双曲线将平面分割为三个部分，我们命名焦点一侧的区域为“双曲线内部”，另一个连通区域为“外部”. 由双曲线定义蕴含以下事实：
当 
 点位于双曲线内部时， 
 ；
当 
 点位于双曲线上面时， 
 ；
当 
 点位于双曲线外部时， 
 ；
而切线 
 上仅有一点 
 满足 
 ，其余各点 
 皆有 
 ，所以 
 是切线 
 上的最大值点，也就是使得
由上引理，必有 
 平分 
 .
参考
^希尔伯特《直观几何》

			
    有时候，一个看似更加复杂的问题反而有一个更简单的解答。

    四色问题是说，对一个平面地图进行染色，要想用不同的颜色来区别相邻的区域，最少需要多少种颜色。在很长一段时间里，人们猜想，只要四种颜色就足够了；但这个“四色猜想”却怎么也证不出来。直到上世纪70年代，“四色猜想”才在计算机的帮助下获得证明。在《从一到无穷大》一书中，作者提到了这样一个有趣的事实：平面上的四色问题一直是一个相当复杂的难题，然而有意思的是，在环面上的染色问题却只需要短短十几行文字就能得出一个完美的结论。下面我们来说明，给一个游泳圈上任意划分出来的区域进行染色，为了使相邻区域不同色，只需要7种颜色就够了。

    为了证明这一点，我们只需要说明，在一个环面图中总能找到一块区域，它的邻域不超过6块。如果真是这样的话，余下的部分用数学归纳法就直接证到了：对于一个有n个区域的图，我们找出它的一个邻域数量不超过6的区域，然后把这块区域缩小为一个点，使整个图的区域个数减少到n-1。按照我们的数学归纳，这个有n-1个区域的图是可以7染色的；并且显然地，把第n个区域添加回去后所产生的图仍然可以7染色，因为我的邻域不超过6个，我总能找一个和这些邻域都不一样的颜色。

    现在的问题就是，为什么总存在邻域数量不超过6的区域呢？注意到在环面上，有V+F-E=0，其中V表示顶点数，F表示区域数，E表示边的总条数。注意到每个顶点都发射出了至少三条边，即所有顶点引出的边数至少为3V；但每条边都被重复计算了一次（因为一条边有两个端点），因此3V/2≤E，即3V≤2E。代入V+F-E=0，得到E≤3F。假设每个区域都有7个或7个以上的邻域，那么它们将产生至少7F条边；但每条边都被重复计算了一次（因为每条边都为两块区域共享），因此7F/2≤E，即7F≤2E。于是，2E≥7F>6F≥2E，矛盾。


    事实上，7种颜色是必需的。构造一个至少需要7种颜色才能染色的环面是一件非常有趣的事情。其实，只要你想到了下面这一点，构造这样的环面是非常容易的：把游泳圈剪断并拉成一根空心的管子，再从中间破开来摊成一个长方形，所谓的“环面”实际上就是一个特殊的矩形平面区域——它的上下和左右是“通的”。下面这个图是从Wikipedia上找来的，它告诉了你如何制作一个7块区域两两相邻的环面。