洛谷P7901题解

· · 题解

题目描述

在一个 2n\times 2n 的矩阵中走 k 步，每一轮每个点只能走一次，求出经过点 (x,y) 的最少次数。（一轮的定义为经过矩阵中所有的点）

题解

数据范围是 10^{18}，显然是一道数学/找规律题。因为矩阵中有 2n\times2n 个点，且必定存在一个点，使得最后经过的点为给定的点，所以我们不难得到此题的公式为 \dfrac{k}{4n^2}。
可能有人会对上面的深色字体有疑问，下面我们来简要证明一下：如果从 (x,y) 开始走能遍历整张图，那从最后到达的那个点反向走回来就必定到达 (x,y)。现在问题转为证明在 2n\times2n 的矩阵中，从任意一个点开始走都能遍历整张图。
如果我们对这张图进行黑白染色，就会得到 2n 个黑点和 2n 个白点。不难发现，每次操作都是从一个点走到它的异色点，又因为两种颜色的点个数相同，所以必定能遍历整张图，原命题得证。

代码如下：

#include<bits/stdc++.h>
using namespace std;
long long n,k,x,y;
int main()
{
    scanf("%lld%lld%lld%lld",&n,&k,&x,&y);
    printf("%lld\n",k/4/n/n);
    return 0;
}