test/yukicoder/599.test.cpp

View this file on GitHub
Last update: 2021-02-04 23:16:22+09:00
Problem: https://yukicoder.me/problems/no/599

Depends on

Code

#define PROBLEM "https://yukicoder.me/problems/no/599"

#include "../../src/RollingHash.hpp"

#include <iostream>
#include <iomanip>

using namespace std;

struct init {
	init() {
		cin.tie(nullptr); ios::sync_with_stdio(false);
		cout << fixed << setprecision(10);
	}
} init_;

int main() {

    string S;
    cin >> S;
    int sz = S.size();
    RollingHash rh(S);

    vector<mint> dp(sz / 2 + 1, 0);
    dp[0] = 1;
    for (int i = 1; i <= sz / 2; i++) {
        for (int j = 1; j <= i; j++) {
            if (rh.get(i - j, i) == rh.get(sz - i, sz - (i - j))) {
                dp[i] += dp[i - j];
            }
        }
    }

    mint ans = 0;
    for (int i = 0; i < sz / 2 + 1; i++)  ans += dp[i];
    cout << ans;

    return 0;
}

#line 1 "test/yukicoder/599.test.cpp"

#define PROBLEM "https://yukicoder.me/problems/no/599"

#line 2 "src/RollingHash.hpp"

#include <vector>
#include <string>

#line 2 "src/Modint.hpp"

#include <cassert>
#include <iostream>
#include <numeric>

using namespace std;
using lint = long long;

template<const int &Modulo>
struct Mint {

    lint val;
    constexpr Mint(lint v = 0) noexcept: val(v % Modulo) { if (val < 0) val += Modulo; }

    constexpr Mint &operator+=(const Mint &r) noexcept {
        val += r.val;
        if (val >= Modulo) val -= Modulo;
        return *this;
    }
    constexpr Mint &operator-=(const Mint &r) noexcept {
        val -= r.val;
        if (val < 0) val += Modulo;
        return *this;
    }
    constexpr Mint &operator*=(const Mint &r) noexcept {
        val = val * r.val % Modulo;
        return *this;
    }
    constexpr Mint &operator/=(const Mint &r) noexcept {
        lint a{r.val}, b{Modulo}, u{1}, v{0};
        while (b) {
            lint t = a / b;
            a -= t * b;
            a ^= b, b ^= a, a ^= b;
            u -= t * v;
            u ^= v, v ^= u, u ^= v;
        }
        assert(a == 1);
        val = val * u % Modulo;
        if (val < 0) val += Modulo;
        return *this;
    }

    constexpr Mint operator+(const Mint &r) const noexcept { return Mint(*this) += r; }
    constexpr Mint operator-(const Mint &r) const noexcept { return Mint(*this) -= r; }
    constexpr Mint operator*(const Mint &r) const noexcept { return Mint(*this) *= r; }
    constexpr Mint operator/(const Mint &r) const noexcept { return Mint(*this) /= r; }

    constexpr Mint operator-() const noexcept { return Mint(-val); }

    constexpr bool operator==(const Mint &r) const noexcept { return val == r.val; }
    constexpr bool operator!=(const Mint &r) const noexcept { return !((*this) == r); }
    constexpr bool operator<(const Mint &r) const noexcept { return val < r.val; }

    constexpr friend ostream &operator<<(ostream &os, const Mint<Modulo> &x) noexcept { return os << x.val; }
    constexpr friend istream &operator>>(istream &is, Mint<Modulo> &x) noexcept {
        lint tmp{};
        is >> tmp;
        x = Mint(tmp);
        return is;
    }

    [[nodiscard]] constexpr Mint pow(lint n) const noexcept {
        Mint res{1}, tmp{*this};
        while (n > 0) {
            if (n & 1) res *= tmp;
            tmp *= tmp;
            n >>= 1;
        }
        return res;
    }
};

constexpr int MOD = 1000000007;
using mint = Mint<MOD>;

int RMOD;
using rmint = Mint<RMOD>;
#line 7 "src/RollingHash.hpp"

using namespace std;

//// mod, base from https://gist.github.com/privet-kitty/295ac9202b7abb3039b493f8238bf40f
class RollingHash {
public:
    explicit RollingHash(const string &s) : sz(s.size()) {

        hash1.assign(sz + 1, 0);
        pow1.assign(sz + 1, 1);
        hash2.assign(sz + 1, 0);
        pow2.assign(sz + 1, 1);

        for (int i = 0; i < sz; i++) {
            hash1[i + 1] = hash1[i] * base1 + s[i];
            pow1[i + 1] = pow1[i] * base1;
            hash2[i + 1] = hash2[i] * base2 + s[i];
            pow2[i + 1] = pow2[i] * base2;
        }
    }

    [[nodiscard]] pair<int, int> get(int l, int r) {
        int res1 = (hash1[r] - hash1[l] * pow1[r - l]).val;
        int res2 = (hash2[r] - hash2[l] * pow2[r - l]).val;
        return {res1, res2};
    }

private:
    static constexpr int prime = 2147483647;
    static constexpr int base1 = 2147483634;
    static constexpr int base2 = 2147483627;
    using Mod = Mint<prime>;

    vector<Mod> hash1, pow1;
    vector<Mod> hash2, pow2;
    int sz;
};
#line 5 "test/yukicoder/599.test.cpp"

#line 7 "test/yukicoder/599.test.cpp"
#include <iomanip>

using namespace std;

struct init {
	init() {
		cin.tie(nullptr); ios::sync_with_stdio(false);
		cout << fixed << setprecision(10);
	}
} init_;

int main() {

    string S;
    cin >> S;
    int sz = S.size();
    RollingHash rh(S);

    vector<mint> dp(sz / 2 + 1, 0);
    dp[0] = 1;
    for (int i = 1; i <= sz / 2; i++) {
        for (int j = 1; j <= i; j++) {
            if (rh.get(i - j, i) == rh.get(sz - i, sz - (i - j))) {
                dp[i] += dp[i - j];
            }
        }
    }

    mint ans = 0;
    for (int i = 0; i < sz / 2 + 1; i++)  ans += dp[i];
    cout << ans;

    return 0;
}