# 2021广东工业大学十月月赛 F-hnjhd爱序列(F-hnjhd love series of October 2021 Guangdong University of Technology)-其他

## 2021广东工业大学十月月赛 F-hnjhd爱序列(F-hnjhd love series of October 2021 Guangdong University of Technology)

``````#include <iostream>
using namespace std;
typedef long long ll;
const int N = 4e5 + 10;
ll s[N], pre[N], buk[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll m, ans = 0, fl = 0, fr = 0;
cin >> m;
for (int i = 1; i <= m; ++i)
{
cin >> s[i];
}
for (int i = m; i >= 1; --i)
{
pre[i] = pre[i + 1] + s[i];
}
for (int i = m; i >= 1; --i)
{
if (pre[i] % m == 0)
{
cout << i << " " << m << endl;
break;
}
if (buk[pre[i] % m] != 0)
{
cout << i << " " << buk[pre[i] % m] - 1 << endl;
break;
}
buk[pre[i] % m] = i;
}
return 0;
}``````
————————

Title: gdutoj | hnjhd love sequence (gdutcode. CN)

At first, I used double pointers to traverse from tail to head, but I found that it would tle!!

Later, the < strong > friend @ 77 < / strong > gave a bucket method, which is equivalent to trading space for time.

One of the principles used is: if two numbers are congruent to x, the difference between the two numbers must be divided by X;

So the suffix sum is used. When the two suffix sums are congruent to m, the difference between the two suffix sums, that is, the sum of that sequence, can be divided by m! (really wonderful)

code:

``````#include <iostream>
using namespace std;
typedef long long ll;
const int N = 4e5 + 10;
ll s[N], pre[N], buk[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll m, ans = 0, fl = 0, fr = 0;
cin >> m;
for (int i = 1; i <= m; ++i)
{
cin >> s[i];
}
for (int i = m; i >= 1; --i)
{
pre[i] = pre[i + 1] + s[i];
}
for (int i = m; i >= 1; --i)
{
if (pre[i] % m == 0)
{
cout << i << " " << m << endl;
break;
}
if (buk[pre[i] % m] != 0)
{
cout << i << " " << buk[pre[i] % m] - 1 << endl;
break;
}
buk[pre[i] % m] = i;
}
return 0;
}``````