#include <bits/stdc++.h>
#include "brperm.h"
using namespace std;
ifstream fin("brperm.in");
ofstream fout("brperm.out");
vector<int> bases = {31,29};
const int mod = 1e9 + 7;
const int lgmax = 18;
const int maxn = 5e5;
struct Mint
{
int val;
Mint(int x = 0)
{
val = x % mod;
}
Mint(long long x)
{
val = x % mod;
}
Mint operator +(Mint oth)
{
return val + oth.val;
}
Mint operator -(Mint oth)
{
return val - oth.val + mod;
}
Mint operator *(Mint oth)
{
return 1ll * val * oth.val;
}
};
Mint powmod(int a, int b)
{
if(b==0)
{
return 1;
}
if(b%2==1)
{
return powmod(a,b-1) * a;
}
Mint P = powmod(a,b/2);
return P * P;
}
Mint dp[2][lgmax+1][maxn+1];
Mint adam[2][lgmax+1][maxn+1];
Mint hashig[2][maxn+1];
Mint powers[2][maxn+1];
Mint inverses[2][maxn+1];
void init(int n, string S)
{
string s;
for(int i= 0 ; i < n; ++i)
{
s+=S[i];
}
s = '$' + s;
for(int t = 0; t < 2; ++t)
{
powers[t][0] = 1;
for(int i=1; i <=n; ++i)
{
powers[t][i] = powers[t][i-1] * bases[t];
}
inverses[t][0] = 1;
Mint invbase = powmod(bases[t],mod-2);
for(int i= 1; i <=n; ++i)
{
inverses[t][i] = inverses[t][i-1] * invbase;
}
for(int i = 1; i <=n; ++i)
{
hashig[t][i] = hashig[t][i-1] + powers[t][i-1] * (s[i]-'a'+1);
}
}
for(int t = 0; t < 2; ++t)
{
for(int i=1; i <=n; ++i)
{
for(int j = 0; j <= lgmax; ++j)
{
dp[t][j][i] = (s[i]-'a'+1);
}
adam[t][0][i] = dp[t][0][i];
}
for(int j = 1; j <= lgmax; ++j)
{
for(int i = 1; i + (1<<j)-1 <= n; ++i)
{
Mint mybase = bases[t];
for(int k = 0; k <= lgmax - j; ++k)
{
dp[t][k][i] = dp[t][k+1][i] + dp[t][k+1][i+(1<<(j-1))] * mybase;
mybase = mybase * mybase;
}
adam[t][j][i] = dp[t][0][i];
}
}
}
}
int query(int st, int k)
{
st++;
int dr = st+(1<<k)-1;
for(int t = 0; t < 2; ++t){
Mint x = (hashig[t][dr] - hashig[t][st-1]) * inverses[t][st-1];
if(x.val != adam[t][k][st].val){
return false;
}
}
return true;
}
Compilation message
/usr/bin/ld: /tmp/ccDq1Jhx.o: in function `main':
grader.cpp:(.text.startup+0x72): undefined reference to `init(int, char const*)'
collect2: error: ld returned 1 exit status
