三次方枚举卡住左方，下方，以及右方/上方，再一个for计算矩形内的点，n^4暴力。
其实枚举前两个之后，每个点要求的len是固定的，按这个sort能达到n^3 lg n的复杂度。
这题比赛的时候没有过是很不应该的……就是一个很典型的dp。回忆一下这场SRM的过程，总结了一下为什么写这种计数自己经常会写但写得很慢。得出以下几点：
- 我想的过程中，经常会陷入局部情况或者说特例的求解，这样弄得最后整个代码就非常混乱，往往写出很多种情况，而这会极大的降低编码的效率。
- 组合计数问题，对独立的步骤进行划分是尤为重要的。而不同情况下每个步骤的操作都是类似的。把类似的过程统一处理往往能得到事半功倍的效果。
- 总得来看，其实这是architecture上的失败和大局观上的失败。
既然意识到了这个问题，那就在以后练习/比赛的时候注意提高吧。
算法大致是分小环和大环dp。
小环通过一个函数统一处理：count(int x, int y, int n, bool o)。这个函数返回的是，在小环上，一个接口在x号点，另一个接口在y号点，整个环的人数是n，x接口和y接口的颜色是否相等时的方案数。这个conut可以通过递推进行预处理(只和两条独立的链有关)。
然后在大环上，用g[i][j]表示处理完前i个小环，给下面的接口的颜色和“第0个环给第n-1个环的颜色”是否相等。再次递推。
最后输出g[n-1][0]即可。
这题就是给定N, M, goalX, goalY求下面这个函数……
- 当i = goalX, j = goalY, f(i, j) = 0
- 其他情况 f(i, j) = (f((i + 1) % N, j) + f(i, (j + 1) % M)) / 2 + 1
输出f(0, 0)即可。
规模有100，迭代是可行的一个做法。
但是这样的迭代是过不了的……
clr(f, 0);
rep (it, 10000) {
rep (i, N) rep (j, M) {
if (i != goalX || j != goalY) {
int ni = (i + 1) % N, nj = (j + 1) % M;
f[i][j] = 1 + (f[ni][j] + f[i][nj]) / 2;
}
}
}
这是因为顺序不科学导致的……因为(goalX, goalY)才是不动点，这样盲目地走看上去就很悲剧。
假设现在我在goalX, goalY，那么我影响到的路线应当是沿着-1方向过来的。
所以改成下面这样迭代顺序就过了。
clr(f, 0);
rep (it, 10000) {
rep (_i, N) rep (_j, M) {
int i = goalX - _i, j = goalY - _j;
if (i < 0) i += N;
if (j < 0) j += M;
if (i != goalX || j != goalY) {
int ni = (i + 1) % N, nj = (j + 1) % M;
f[i][j] = 1 + (f[ni][j] + f[i][nj]) / 2;
}
}
}
除了迭代以外，对于这种互相依赖的关系，迭代矩阵的又是满秩的，高斯消元解方程也是一个选择。那么假设M+N-1个未知量，其中M个在同一行，N个在同一列(为了方便，最好把不动点放在交错的位置)。这样其它的所有函数值都可以表示为这N+M-1个未知量的线性组合。绕了一圈一个，就可以得到M+N级别个方程，而M+N只有200，高斯消元是没有压力的。
但是zYc大师说好像有问题，等下写个代码看看能不能过。
更新
这个高斯消元算法是可以AC的。
代码在此