二维反射容斥：P9366

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133707260

https://www.luogu.com.cn/problem/P9366

构造循环矩阵，考虑反射容斥和将军饮马

在这里插入图片描述

考虑二维不太好做，我们曼哈顿距离转切比雪夫距离，变成一维的情况。

由于棋盘是正方形的，所以循环长度为 2n+42n+4 。用多项式快速幂预处理，询问记得考虑正负两个方向。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
auto kuai(int T) {
	if(T==0) return atcoder :: Poly({1}); 
	auto p = kuai(T/2); 
	p *= p; 
	for(int i=M; i < p.size(); ++i) p[i-M]+=p[i]; 
	p = p.modxk(M); 
	
	if(T % 2 == 0) return p; 
	
	p = p.mulxk(1) + p.mulxk(M-1);  
	for(int i=M; i < p.size(); ++i) p[i-M]+=p[i]; 
	p = p.modxk(M); 
	
	return p; 
}


signed main()
{
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
//	T=read();
//	while(T--) {
//
//	}
	n=read(); T=read(); q=read(); 
	N=2*(n+1)+2; M=2*N; 
	auto res = kuai(T); 
	auto Go = [&] (int u0, int v0, int u1, int v1) {
		int dx = ( ((u1+v1) - (u0+v0)) % M + M)%M; 
		int dy = ( ((u1-v1) - (u0-v0)) % M + M)%M; 
//		printf("%lld %lld | %lld %lld\n", res[dx].x, res[dy].x, res[(dx+N)%M], res[(dy+N)%M]); 
		return res[dx] * res[dy] + res[(dx+N)%M] * res[(dy+N)%M]; 
	}; 
	while(q--) {
		u0 = read(); v0 = read(); 
		u1 = read(); v1 = read(); 
		auto ans = Go(u0, v0, u1, v1); 
		ans -= Go(u0, v0, N - 2 - u1, v1); 
		ans -= Go(u0, v0, u1, N - 2 - v1); 
		ans += Go(u0, v0, N - 2- u1, N - 2 - v1); 
		printf("%lld\n", ans.x); 
	}
	return 0;
}