#935957 (C++23) No.599 回文かい

• 問題: No.599 回文かい
• ユーザー: Ramurata
• 提出日時: 2023-12-03 18:53:34
• 言語: C++23 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 1,802 ms / 4,000 ms
• コード長: 12,873 bytes
• コンパイル時間: 3,546 ms
• コンパイル使用メモリ: 259,324 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-09-26 22:13:58
• 合計ジャッジ時間: 7,419 ms
• ジャッジサーバーID （参考情報）: judge2 / judge5

ファイルパターン	結果
other	AC * 22

ソースコード

#include <bits/stdc++.h>
using namespace std;
void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); return 0;}
#define overload4(_1, _2, _3, _4, name, ...) name
#define rep1(i, n) for (int i = 0; i < int(n); ++i)
#define rep2(i, s, n) for (int i = int(s); i < int(n); ++i)
#define rep3(i, s, n, d) for(int i = int(s); i < int(n); i+=d)
#define rep(...) overload4(__VA_ARGS__,rep3,rep2,rep1)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define SUM(a) accumulate(all(a),0LL)
#define MIN(a) *min_element(all(a))
#define MAX(a) *max_element(all(a))
#define INT(...) int __VA_ARGS__;input(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;input(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;input(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__;input(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__;input(__VA_ARGS__)
#define LD(...) ld __VA_ARGS__;input(__VA_ARGS__)
#define pb push_back
#define eb emplace_back
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using vi = std::vector<int>;
using vvi = std::vector<vi>;
using vl = std::vector<ll>;
using vvl = std::vector<vl>;
using vd = std::vector<double>;
using vvd = std::vector<vd>;
using vs = std::vector<std::string>;
using vvs = std::vector<vs>;
using vb = std::vector<bool>;
using vvb = std::vector<vb>;
using vc = std::vector<char>;
using vvc = std::vector<vc>;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;
using mii = std::map<int, int>;
using mll = std::map<ll, ll>;
template<typename T>
struct infinity{
    static constexpr T max=std::numeric_limits<T>::max();
    static constexpr T min=std::numeric_limits<T>::min();
    static constexpr T value=std::numeric_limits<T>::max()/2;
    static constexpr T mvalue=std::numeric_limits<T>::min()/2;
};
template<typename T>constexpr T INF=infinity<T>::value;
constexpr ll infl=INF<ll>;
constexpr int inf = INF<int>;
constexpr ld PI = 3.1415926535897932384626;
template<typename T,typename U>
std::istream &operator>>(std::istream&is,std::pair<T,U>&p){is>>p.first>>p.second;return is;}
template<typename T>
std::istream &operator>>(std::istream&is,std::vector<T>&v){for(T &in:v){is>>in;}return is;}
inline void scan(int &a) { std::cin >> a; }
inline void scan(long long &a) { std::cin >> a; }
inline void scan(std::string &a) { std::cin >> a; }
inline void scan(char &a) { std::cin >> a; }
inline void scan(double &a) { std::cin >> a; }
inline void scan(long double &a) { std::cin >> a; }
template <class T, class U>
inline void scan(std::pair<T, U> &p) { std::cin >> p; }
template <class T>
inline void scan(std::vector<T> &a) { std::cin >> a; }
inline void input() {}
template <class Head, class... Tail>
inline void input(Head &head, Tail &...tail) {scan(head);input(tail...);}
template<typename T>
std::ostream &operator<<(std::ostream&os,const std::vector<T>&v){for(auto it=std::begin(v);it!=std::end(v);){os<<*it<<((++it)!=std::end(v)?" ":"");}return os;}
template<typename T,typename U>
std::ostream &operator<<(std::ostream&os,const std::pair<T,U>&p){os<<p.first<<" "<<p.second;return os;}
template<class T>
inline void print(const T &t){std::cout<<t<<'\n';}
template<class Head, class... Tail>
inline void print(const Head &head, const Tail &... tail){std::cout<<head<<' ';print(tail...);}
template<class... T>
inline void fin(const T &... a){print(a...);exit(0);}
template<class T>
inline void printl(const T &t){std::cout<<t<<'\n';}
template <class T>
inline void printl(const std::vector<T> &a){for(const auto &v : a) std::cout << v << '\n';}
template<class Head, class... Tail>
inline void printl(const Head &head, const Tail &... tail){std::cout<<head<<' ';print(tail...);}
inline void Yes(const bool b = true) { std::cout << (b ? "Yes\n" : "No\n"); }
inline void No() { std::cout << "No\n"; }
inline void YES(const bool b = true) { std::cout << (b ? "YES\n" : "NO\n"); }
inline void NO() { std::cout << "NO\n"; }
template<class T>
void trace(const T &t){std::cerr<<t<<')'<<'\n';}
template<class Head, class... Tail>
void trace(const Head &head, const Tail &... tail){std::cerr<<head<<' ';trace(tail...);}
#ifdef ONLINE_JUDGE
#define debug(...) (void(0))
#else
#define debug(...) do{std::cerr<<'('<<#__VA_ARGS__<<") = (";trace(__VA_ARGS__);}while(0)
#endif
template<class... T>
constexpr auto my_max(T... a){ return max(initializer_list<common_type_t<T...>>{a...}); }
template<class... T>
constexpr auto my_min(T... a){ return min(initializer_list<common_type_t<T...>>{a...}); }
template<typename T, typename U> bool chmin(T &a, U b) {if (a>b) {a=b;return true;}return false;}
template<typename T, typename U> bool chmax(T &a, U b) {if (a<b) {a=b;return true;}return false;}
template<class T>
std::vector<std::vector<T>> ROTATE(std::vector<std::vector<T>> X) {
    if(X.size() == 0) return X;
    std::vector<vector<T>> res(X[0].size(),std::vector<T>(X.size()));
    rep(i,X.size())rep(j,X[0].size())res[j][X.size()-i-1]=X[i][j];
    return res;
}
template<typename T>
struct CumulativeSum {
private:    
    std::vector<T> data;
    bool sorted = false;
public:
    CumulativeSum(int n) : data(n + 1, 0) {}
    CumulativeSum(const std::vector<T> &v) : data(v.size() + 1, 0) {
        for(int i = 0; i < (int)v.size(); i++) add(i, v[i]);
    }
    void add(int k, const T &val) { data[k + 1] += val; }
    void build() {
        assert(!sorted); sorted = true;
        for(int i = 1; i < (int)data.size(); i++) data[i] += data[i - 1];
    }
    T prod(int r) {
        assert(sorted);
        return (r < 0 ? 0 : data[min(r, (int)data.size() - 1)]);
    }
    T prod(int l, int r) {
        assert(sorted);
        return prod(r) - prod(l); 
    }
};
inline constexpr bool is_prime(ll n){
    if(n<=1)return false;
    for(ll i=2;i*i<=n;i++){
        if(n%i==0)return false;
    }
    return true;
}
inline constexpr ll my_pow(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1)res*=a;
        a*=a;
        b>>=1;
    }
    return res;
}
inline constexpr ll mod_pow(ll a,ll b,const ll&mod){
    if(mod==1)return 0;
    a%=mod;
    ll res=1;
    while(b){
        if(b&1)(res*=a)%=mod;
        (a*=a)%=mod;
        b>>=1;
    }
    return res;
}
/**
 * @brief RollingHash
 */
struct RollingHash {
private:
    static const uint64_t mod = (1ull << 61ull) - 1;
    using uint128_t = __uint128_t;
    std::vector<uint64_t> power;
    const uint64_t base;
    static inline uint64_t add(uint64_t a, uint64_t b) {
        if((a += b) >= mod) a -= mod;
        return a;
    }
    static inline uint64_t mul(uint64_t a, uint64_t b) {
        uint128_t c = (uint128_t)a * b;
        return add(c >> 61, c & mod);
    }
    static inline uint64_t generate_base() {
        std::mt19937_64 mt(std::chrono::steady_clock::now().time_since_epoch().count());
        std::uniform_int_distribution< uint64_t > rand(1, RollingHash::mod - 1);
        return rand(mt);
    }
    inline void expand(size_t sz) {
        if(power.size() < sz + 1) {
            int pre_sz = (int)power.size();
            power.resize(sz + 1);
            for(int i = pre_sz - 1; i < sz; i++) {
                power[i + 1] = mul(power[i], base);
            }
        }
    }
public:
    RollingHash(uint64_t base = generate_base()) : base(base), power{1} {}
    std::vector<uint64_t> build(const std::string &s) const {
        int sz = s.size();
        std::vector<uint64_t> hashed(sz + 1);
        for(int i = 0; i < sz; i++) {
            hashed[i + 1] = add(mul(hashed[i], base), s[i]);
        }
        return hashed;
    }
    template<typename T>
    std::vector<uint64_t> build(const std::vector<T> &s) const {
        int sz = s.size();
        std::vector<uint64_t> hashed(sz + 1);
        for(int i = 0; i < sz; i++) {
            hashed[i + 1] = add(mul(hashed[i], base), s[i]);
        }
        return hashed;
    }
    uint64_t hash(const std::vector<uint64_t> &s, int l, int r) {
        expand(r - l);
        return add(s[r], mod - mul(s[l], power[r - l]));
    }
    uint64_t all_hash(const std::vector<uint64_t> &s) {
        return s.back();
    }
};
/**
 * @brief ModInt
 */
template<std::size_t size>
struct uint_least{
    static_assert(size<=128,"size must be less than or equal to 128");
    using type=typename std::conditional<
        size<=8,std::uint_least8_t,
        typename std::conditional<
            size<=16,std::uint_least16_t,
            typename std::conditional<
                size<=32,std::uint_least32_t,
                typename std::conditional<size<=64,std::uint_least64_t,__uint128_t>::type>::type>::type>::type;
};
template<std::size_t size> using uint_least_t = typename uint_least<size>::type;
namespace internal{
    struct modint_base{};
}//naespace internal
template<typename T>using is_modint = std::is_base_of<internal::modint_base,T>;
template<typename T,T mod>
struct StaticModInt:internal::modint_base{
    static_assert(std::is_integral<T>::value, "T must be integral");
    static_assert(std::is_unsigned<T>::value, "T must be unsgined");
    static_assert(mod>0, "mod must be positive");
    static_assert(mod<=INF<T>, "mod*2 must be less than or equal to T::max()");
    private:
    using large_t = typename uint_least<std::numeric_limits<T>::digits * 2>::type;
    using signed_t = typename std::make_signed<T>::type;
    T val;
    public:
    constexpr StaticModInt():val(0){}
    template<typename U,typename std::enable_if<std::is_integral<U>::value&&std::is_unsigned<U>::value>::type* =nullptr>
    constexpr StaticModInt(U x):val(x%mod){}
    template<typename U,typename std::enable_if<std::is_integral<U>::value&&std::is_signed<U>::value>::type* =nullptr>
    constexpr StaticModInt(U x):val{}{
        x%=static_cast<signed_t>(mod);
        if(x<0)x+=static_cast<signed_t>(mod);
        val=static_cast<T>(x);
    }
    T get()const{return val;}
    static constexpr T get_mod(){return mod;}
    static StaticModInt raw(T v){
        StaticModInt res;
        res.val=v;
        return res;
    }
    StaticModInt inv()const{
        return mod_inv(val,mod);
    }
    StaticModInt& operator++(){
        ++val;
        if(val==mod)val=0;
        return *this;
    }
    StaticModInt operator++(int){
        StaticModInt res=*this;
        ++*this;
        return res;
    }
    StaticModInt& operator--(){
        if(val==0)val=mod;
        --val;
        return *this;
    }
    StaticModInt operator--(int){
        StaticModInt res=*this;
        --*this;
        return res;
    }
    StaticModInt& operator+=(const StaticModInt&x){
        val+=x.val;
        if(val>=mod)val-=mod;
        return *this;
    }
    StaticModInt& operator-=(const StaticModInt&x){
        if(val<x.val)val+=mod;
        val-=x.val;
        return *this;
    }
    StaticModInt& operator*=(const StaticModInt&x){
        val=static_cast<T>((static_cast<large_t>(val)*x.val)%mod);
        return *this;
    }
    StaticModInt& operator/=(const StaticModInt&x){
        return *this*=x.inv();
    }
    friend StaticModInt operator+(const StaticModInt&l,const StaticModInt&r){return StaticModInt(l)+=r;}
    friend StaticModInt operator-(const StaticModInt&l,const StaticModInt&r){return StaticModInt(l)-=r;}
    friend StaticModInt operator*(const StaticModInt&l,const StaticModInt&r){return StaticModInt(l)*=r;}
    friend StaticModInt operator/(const StaticModInt&l,const StaticModInt&r){return StaticModInt(l)/=r;}
    StaticModInt operator+()const{return StaticModInt(*this);}
    StaticModInt operator-()const{return StaticModInt()-*this;}
    friend bool operator==(const StaticModInt&l,const StaticModInt&r){return l.val==r.val;}
    friend bool operator!=(const StaticModInt&l,const StaticModInt&r){return l.val!=r.val;}
    StaticModInt pow(long long a)const{
        StaticModInt v=*this,res=1;
        while(a){
            if(a&1)res*=v;
            v*=v;
            a>>=1;
        }
        return res;
    }
    friend std::ostream &operator<<(std::ostream &os,const StaticModInt&x){
        return os<<x.val;
    }
    friend std::istream &operator>>(std::istream &is,StaticModInt&x){
        long long tmp;
        is>>tmp;
        x=StaticModInt(tmp);
        return is;
    }
};
template<unsigned int p>using ModInt=StaticModInt<unsigned int,p>;
using modint998244353 = ModInt<998244353>;
using modint1000000007 = ModInt<1000000007>;
using mint = modint1000000007;
void _main() {
    RollingHash rh;
    STR(S);
    auto ht = rh.build(S);
    map<pii, mint> memo;
    function<mint(int, int)> dfs = [&](int l, int r) {
        if(r < l) return mint(1);
        if(memo.find({l, r}) != memo.end()) return memo[{l, r}];
        mint res = 1;
        int L = l, R = r;
        while(L < R) {
            if(rh.hash(ht, l, L + 1) == rh.hash(ht, R, r + 1)) res += dfs(L + 1, R - 1);
            L++, R--;
        }
        return memo[{l, r}] = res;
    };
    print(dfs(0, S.size() - 1));
}