如何做网站发布商品_专门的网页制作工具有()_营销图片素材_百度seo怎么做网站内容优化

D. Pedometer

        先断环成链，然后从 n 开始一直到 2n - 1，判断一下前缀和。n^2 做法

 

for (int i = n; i < 2 * n; i ++)for (int j = i - n + 1; j < i; j ++)if (d[i] - d[j - 1] % m == 0)ans ++;

 

        注意到取模的性质，也就是 d [ i ] % m == d [ j - 1 ] % m，因此只需要统计一下模数相等的就可以了。

        注意滑动窗口两端要同时更新。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 5, INF = 1e18;int T, n, m, cnt, ans, a[N * 2], d[N * 2];
map<int, int> mp;signed main()
{cin >> n >> m;for (int i = 1; i <= n; i ++){cin >> a[i];a[i + n] = a[i];}for (int i = 1; i <= 2 * n; i ++){d[i] = d[i - 1] + a[i];d[i] %= m;}for (int i = 1; i < n; i ++)mp[d[i]] ++;for (int i = n; i < 2 * n; i ++){if (mp.count(d[i]) != 0)ans += mp[d[i]];mp[d[i - n + 1]] --;mp[d[i]] ++;}cout << ans;return 0;
}