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

提出ソース

結果

問題	No.599 回文かい
ユーザー	Ramurata
提出日時	2023-12-03 16:59:34
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	1,879 ms / 4,000 ms
コード長	8,677 bytes
コンパイル時間	3,319 ms
コンパイル使用メモリ	261,776 KB
実行使用メモリ	6,676 KB
最終ジャッジ日時	2023-12-03 16:59:42
合計ジャッジ時間	7,834 ms
ジャッジサーバーID （参考情報）	judge12 / judge13

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,676 KB
testcase_01	AC	2 ms 6,676 KB
testcase_02	AC	1 ms 6,676 KB
testcase_03	AC	2 ms 6,676 KB
testcase_04	AC	2 ms 6,676 KB
testcase_05	AC	2 ms 6,676 KB
testcase_06	AC	2 ms 6,676 KB
testcase_07	AC	1 ms 6,676 KB
testcase_08	AC	2 ms 6,676 KB
testcase_09	AC	2 ms 6,676 KB
testcase_10	AC	2 ms 6,676 KB
testcase_11	AC	2 ms 6,676 KB
testcase_12	AC	2 ms 6,676 KB
testcase_13	AC	2 ms 6,676 KB
testcase_14	AC	73 ms 6,676 KB
testcase_15	AC	6 ms 6,676 KB
testcase_16	AC	1,681 ms 6,676 KB
testcase_17	AC	1,879 ms 6,676 KB
testcase_18	AC	2 ms 6,676 KB
testcase_19	AC	1 ms 6,676 KB
testcase_20	AC	2 ms 6,676 KB
evil_0.txt	AC	33 ms 6,676 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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();
    }
};
#include <atcoder/modint>
using mint = atcoder::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;
    };
    cout << dfs(0, S.size() - 1).val() << endl;
}

yukicoder

結果

テストケース

ソースコード