题解 AT5334 【[ABC156F] Modularness】
StudyingFather
2020-03-26 00:53:24
正着做似乎不太好办，我们考虑反面情况：即统计 $a_i \bmod m = a_{i+1} \bmod m$ 和 $a_i \bmod m \gt a_{i+1} \bmod m$ 这两种情况的数量。
首先我们做个预处理：将所有的 $d$ 都对 $m$ 取模，容易发现这个操作对结果没有影响。
接下来我们开始统计。
- $a_i \bmod m=a_{i+1} \bmod m$
容易发现只有 $d_{i \bmod k}=0$ 时满足条件。
- $a_i \bmod m \gt a_{i+1} \bmod m$
因为我们将所有 $d$ 都取模了，相当于我们现在进行的是 $m$ 进制运算。
这种情况下可以理解为在 $m$ 进制下发生了进位操作。
一次进位只可能使前一位的值恰好增加 $1$，因此我们只需要统计发生了多少次进位即可。
上面两个操作利用本题的周期性都可以在 $O(k)$ 时间内解决。从而总时间复杂度为 $O(qk)$。
```cpp
// Problem : F - Modularness
// Contest : AtCoder Beginner Contest 156
// URL : https://atcoder.jp/contests/abc156/tasks/abc156_f
// Author : StudyingFather
// Site : https://studyingfather.com
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)
#include <iostream>
using namespace std;
int d[5005],nd[5005];
long long ds[5005];
int main()
{
int k,q;
cin>>k>>q;
for(int i=1;i<=k;i++)
cin>>d[i];
while(q--)
{
int n,x,m,cnt=0,ans;
long long sum;
cin>>n>>x>>m;
n--;
ans=n;
for(int i=1;i<=k;i++)
{
nd[i]=d[i]%m;
ds[i]=ds[i-1]+nd[i];
cnt+=(nd[i]==0);
}
ans-=n/k*cnt;
sum=x+n/k*ds[k]+ds[n%k];
for(int i=1;i<=n%k;i++)
ans-=(nd[i]==0);
ans-=sum/m-x/m;
cout<<ans<<endl;
}
return 0;
}
```