oj.uz

Submission #854644

# Submission time Handle Problem Language Result Execution time Memory
854644 2023-09-28T09:54:19 Z tibinyte Brperm (RMI20_brperm) C++14
0 / 100
 593 ms 90916 KB 
#include <bits/stdc++.h>
using namespace std;
const int base = 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[lgmax+1][maxn+1];
Mint adam[lgmax+1][maxn+1];
Mint hashig[maxn+1];
Mint powers[maxn+1];
Mint inverses[maxn+1];
void init(int n, const char S[])
{
    string s;
    for(int i= 0 ; i < n; ++i){
        s+=S[i];
    }
    s = '$' + s;
    powers[0] = 1;
    for(int i=1; i <=n; ++i){
        powers[i] = powers[i-1] * base;
    }
    inverses[0] = 1;
    Mint invbase = powmod(base,mod-2);
    for(int i= 1; i <=n; ++i){
        inverses[i] = inverses[i-1] * invbase;
    }
    for(int i = 1; i <=n; ++i){
        hashig[i] = hashig[i-1] + powers[i-1] * (s[i]-'a'+1);
    }
    for(int i=1; i <=n; ++i){
        for(int j = 0; j <= lgmax; ++j){
            dp[j][i] = (s[i]-'a'+1);
        }
        adam[0][i] = dp[0][i];
    }
    for(int j = 1; j <= lgmax; ++j){
        for(int i = 1; i + (1<<j)-1 <= n; ++i){
            Mint mybase = base;
            for(int k = 0; k <= lgmax - j; ++k){
                dp[k][i] = dp[k+1][i] + dp[k+1][i+(1<<(j-1))] * mybase;
                mybase = mybase * mybase;
            }
            adam[j][i] = dp[0][i];
        }
    }
}
bool query(int st, int k)
{
    st++;
    int dr = st+(1<<k)-1;
    Mint x = (hashig[dr] - hashig[st-1]) * inverses[st-1];
    return x.val == adam[k][st].val;
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 80476 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 80476 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 593 ms 90916 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 80476 KB Output isn't correct
2 Halted 0 ms 0 KB -