题解：AT_abc367_d [ABC367D] Pedometer

Posted on Edited on

题解：AT_abc367_d [ABC367D] Pedometer

前言

赛时被整懵了，赛后题解。

AtCoder Problem

更好的阅读体验？

翻译

注意：一定是顺时针走。

正文

记 \(i,j\) 的距离为 \(d(i,j)\)

暴力的做法是，枚举 \(\dfrac{d(i,j)}{M}\)，二分查找满足条件的点。

显然过不了，其瓶颈在于倍数的枚举。

不妨破环，记数组 \(a\) 为 \(a_1,a_2,\dots,a_{2N-1}\)，且使用前缀和。

事实上，\(d(i,j) \equiv 0 (\bmod \ M)\) 的充要条件是 \(\sum\limits^{i}_{k=1}a_k\equiv \sum\limits^{j}_{k=1}a_k(\bmod \ M)\)。

故对所有前缀和对 \(M\) 取模，若模相同，则满足题目要求。

但是考虑到一定是顺时针走，我们统计是只从前往后看的。换句话说就是，前面的只会看后面的，不会再往前看。这里的前后指的是下标的大小。

具体的，现有点 \(i,j\)。要从 \(i\) 走到 \(j\)。

  • 若 \(i<j\)，相当于判别 \(\sum\limits^{i}_{k=1}a_k\) 和 \(\sum\limits^{j}_{k=1}a_k\) 模相同。
  • 若 \(i>j\)，相当于判别 \(\sum\limits^{i}_{k=1}a_k\) 和 \(\sum\limits^{j+N}_{k=1}a_k\) 模相同。

我们看到第 \(i\) 个的时候只会向后看到第 \(i+N-1\) 个。因为这样我们才能保证我们即是方向正确的，又是两点的最短路径。

代码实现，我们采用了桶装的方法，因为对 \(M\) 取模的余数一定小于 \(M\)。

代码：

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
#include <bits/stdc++.h>
#define rep(i,l,r) for(int i=(l);i<=(r);i++)

using namespace std;
typedef long long ll;

const int N=2e5+23;
int n,m;
int a[2*N],sum[2*N];
unordered_map<int,int> cnt;

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
    cin>>n>>m;
    rep(i,1,n) cin>>sum[i],sum[i+n]=sum[i];
    rep(i,1,2*n) sum[i]+=sum[i-1],sum[i]%=m;
    rep(i,1,n) cnt[sum[i]]++;  
    ll ans=0;
    rep(i,1,n)
    {
        cnt[sum[i]]--; // 弃用
        ans+=cnt[sum[i]]; // 统计
        cnt[sum[i+n]]++; // 启用
    }
    cout<<ans;
}

AC 记录

总结

我觉得这个放在 D 虽然代码不长，但是有一定难度的。

参考资料：

广告：安利一下我的代码仓库。AtCoder 的部分题目代码即调试信息、避坑可以在这里找到。