NOI.AC省选模拟赛第一场 T1 (树上高斯消元)

link

很容易对于每个点列出式子

\(f_{x,y}=(f_{x,y-1}+f_{x,y}+f_{x,y+1}+f_{x+1,y})/4\)(边角转移类似，略)

这个转移是相互依赖的就gg了

不过你可以把这个转移移项，改成右侧没有\(f_{x,y}\)的式子

不过他还是相互依赖的

但是上下两行之间转移不是依赖的

所以你可以每一行跑一遍高斯消元

由于一行的转移是一条链

树上高斯消元可以做到 \(O(n)\) 或 \(O(n \log p)\)(模意义下逆元)

而链上的情况更简单，直接xjb搞一下就行了

具体是将\(f_{x,y-1}\)和\(f_{x,y}\)之间的线性关系搞出来，然后根据\(f_{x,y}\)的式子将\(f_{x,y+1}\)的线性关系也搞出来

最后你会发现\(f_{x,m-1}\)和\(f_{x,m}\)之间搞出了两个线性关系，就可以解出来了

然后你会发现前面的依次带入进去就行了

丑代码

注意特判m=1

#include <cstdio>

using namespace std;

const int xkj = 998244353, inv2 = 499122177, inv3 = 332748118;

int n, m, val[1010], x[1010];

int k[1010], b[1010];

int qpow(int x, int y)

{

	int res = 1;

	for (x %= xkj; y > 0; y >>= 1, x = x * (long long)x % xkj)

		if (y & 1) res = res * (long long)x % xkj;

	return res;

}

void gao()

{

	if (m == 1) { val[1] += 2; return; }

	k[2] = inv2, b[2] = (val[1] + 3) * (long long)inv2 % xkj;

	for (int i = 2; i <= m - 1; i++) //x[i - 1] = k[i] * x[i] + b[i]

	{

		k[i + 1] = qpow((3 - k[i] + xkj) % xkj, xkj - 2);

		b[i + 1] = (val[i] + b[i] + 4) % xkj * (long long)k[i + 1] % xkj;

	}

	x[m] = (val[m] + b[m] + 3) % xkj * (long long)qpow((2 - k[m] + xkj) % xkj, xkj - 2) % xkj;

	for (int i = m - 1; i >= 1; i--) x[i] = (k[i + 1] * (long long)x[i + 1] % xkj + b[i + 1]) % xkj;

	for (int i = 1; i <= m; i++) val[i] = x[i];

}

int main()

{

	int x, y;

	scanf("%d%d%d%d", &n, &m, &x, &y); n -= x - 1;

	for (int i = 2; i <= n; i++) gao();

	printf("%d\n", val[y]);

	return 0;

}

迷思：树上高斯消元

我们考虑随便拎出一个度数为1的点开始dfs1这个树，在回溯时得到儿子和父亲之间的线性关系

最后你会得到根节点和根节点的儿子之间的两个线性关系，你就可以得到这两个点的值

然后你再dfs2下去，由于线性关系已经确定就可以根据某个点的父亲的值算出这个点的值了

NOI.AC省选模拟赛第一场 T1 (树上高斯消元)的相关教程结束。