Pagini recente » Cod sursa (job #2536085) | Cod sursa (job #2380260) | Cod sursa (job #1525327) | Cod sursa (job #424619) | Cod sursa (job #2245181)
#include <fstream>
#include <vector>
#define BASE 37
#define MOD_1 100007
#define MOD_2 100021
using namespace std;
ifstream in("reguli.in");
ofstream out("reguli.out");
int main()
{
int n;
in >> n;
int rez = n - 2;
vector<long long> nr;
vector<long long> v(n + 1);
vector<long long> Hash_1(n + 1), Hash_2(n + 1);
vector<long long> cnst_1(n + 1), cnst_2(n + 1);
in >> v[1];
for (int i = 2; i <= n; i++)
{
in >> v[i];
nr.push_back(v[i] - v[i - 1]);
}
cnst_1[0] = 1;
cnst_2[0] = 1;
Hash_1[0] = nr[0];
Hash_2[0] = nr[0];
for (int i = 1; i < nr.size(); i++)
{
Hash_1[i] = (Hash_1[i - 1] * BASE + nr[i]) % MOD_1;
Hash_2[i] = (Hash_2[i - 1] * BASE + nr[i]) % MOD_2;
cnst_1[i] = (cnst_1[i - 1] * BASE) % MOD_1;
cnst_2[i] = (cnst_2[i - 1] * BASE) % MOD_2;
}
int st = 0;
int dr = nr.size() - 1;
while (st <= dr)
{
bool OK = true;
bool verif = false;
int mij = (st + dr) / 2;
int var_1 = Hash_1[mij];
int var_2 = Hash_2[mij];
int last;
for (int i = (mij + 1) * 2 - 1; i < nr.size(); i = i + mij + 1)
{
verif = true;
last = i;
if (((Hash_1[i] - (Hash_1[i - mij - 1] * cnst_1[mij + 1]) % MOD_1 + MOD_1) % MOD_1) != var_1)
{
OK = false;
break;
}
if (((Hash_2[i] - (Hash_2[i - mij - 1] * cnst_2[mij + 1]) % MOD_2 + MOD_2) % MOD_2) != var_2)
{
OK = false;
break;
}
}
if (nr.size() % (mij + 1) != 0 && (mij + 1) * 2 < nr.size())
{
int a = ((Hash_1[nr.size() - 1] - (Hash_1[last] * cnst_1[nr.size() - 1 - last]) % MOD_1 + MOD_1) % MOD_1);
int b = ((Hash_2[nr.size() - 1] - (Hash_2[last] * cnst_2[nr.size() - 1 - last]) % MOD_2 + MOD_2) % MOD_2);
int ramas = nr.size() - last - 2;
if (a != Hash_1[ramas] || b != Hash_2[ramas])
OK = false;
}
if (OK == true)
{
if (verif == true)
rez = mij;
dr = mij - 1;
}
else
st = mij + 1;
}
out << rez + 1 << '\n';
for (int i = 0; i < rez + 1; i++)
out << nr[i] << '\n';
return 0;
}