Code Formula 2014 本選 E - ab文字列

問題ページ

文字列の長さは についてフィボナッチ数列になっている。したがって については一意に定まる。また、フィボナッチ数列で20000以下となるのは22番目までなので、 である。文字列は高々 個程度しか存在しないので、 を全列挙し、 と一致するか判定すればよい。

普通に文字列の一致判定に かけているとTLEするのでハッシュを用いて高速化する。ローリングハッシュの要領でハッシュ関数を定めると、文字列 を連結した文字列の のハッシュは高速に求められる。 の値をメモ化再帰で計算していくことで で のハッシュを求められる。

MLには注意

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#define FOR(i, a, n) for(ll i=(ll)a; i<(ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
#ifdef DEBUG  
#include "../program_contest_library/memo/dump.hpp"  
#else  
#define dump(...)  
#endif  
constexpr ll INF = 1LL<<60;  
  
struct dice {  
    mt19937 mt;  
    dice() : mt(chrono::steady_clock::now().time_since_epoch().count()) {}  
    ll operator()(ll x) { return this->operator()(0, x - 1); }  
    ll operator()(ll x, ll y) {  
        uniform_int_distribution<ll> dist(x, y);  
        return dist(mt);  
    }  
} rnd;  
  
class rollingHash {  
private:  
    static constexpr ll mod = (1LL<<61) - 1;  
    const ll base;  
    vector<ll> hash, p;  
  
    ll mul(ll a, ll b) {  
        ll au = a>>31, ad = a & ((1LL<<31)-1);  
        ll bu = b>>31, bd = b & ((1LL<<31)-1);  
        ll mid = ad*bu+au*bd, midu = mid>>30, midd = mid & ((1LL<<30)-1);  
        return au*bu*2 + midu + (midd<<31) + ad*bd;  
    }  
    ll calcmod(ll x) {  
        ll ret = (x>>61) + (x & mod);  
        if(ret >= mod) ret -= mod;  
        return ret;  
    }  
  
public:  
    rollingHash(const string &s) : base(rnd(2, 100000)), hash(s.size()+1), p(s.size()+1,1) {  
        REP(i, s.size()) {  
            hash[i+1] = calcmod(mul(hash[i], base)+s[i]);  
            p[i+1] = calcmod(mul(p[i], base));  
        }  
    }  
    // [l,r)  
    ll get(int l,int r) {  
        return calcmod(hash[r] + 3*mod - mul(hash[l], p[r-l]));  
    }  
    ll concat(ll h1, ll h2, ll h2len) {  
        return calcmod(mul(h1, p[h2len]) + h2);  
    }  
};  
  
int main() {  
    string s;  
    cin >> s;  
      
    if(s.size()==1) {  
        if(s=="a") cout << "2 0\n";  
        else cout << "1 0\n";  
        return 0;  
    }  
  
    rollingHash hash(s);  
    ll ha = -1, hb = -1;  
    REP(i, s.size()) {  
        if(s[i]=='a') ha = hash.get(i, i+1);  
        else if(s[i]=='b') hb = hash.get(i, i+1);  
    }  
    ll hs = hash.get(0, s.size());  
  
    // fib[i] = (f_{ij}の長さ)  
    vector<ll> fib({0, 1, 1, 2});  
    {  
        ll a = 1, b = 1, c = 2;  
        while(c < (ll)s.size()) {  
            a = b;  
            b = c;  
            c = a+b;  
            fib.push_back(c);  
        }  
    }  
    ll n = fib.size()-1;  
  
    vector<vector<ll>> memo(n+1);  
    FOR(i, 3, n+1) memo[i].assign(1LL<<(i-2), -1);  
    auto dfs = [&](auto &&self, ll x, ll y) -> ll {  
        if(x==1) return hb;  
        if(x==2) return ha;  
        if(memo[x][y] != -1) return memo[x][y];  
        if(y%2==0) {  
            auto vl = self(self, x-1, y/2);  
            auto vr = self(self, x-2, y/4);  
            return memo[x][y] = hash.concat(vl, vr, fib[x-2]);  
        } else {  
            auto vl = self(self, x-2, y/4);  
            auto vr = self(self, x-1, y/2);  
            return memo[x][y] = hash.concat(vl, vr, fib[x-1]);  
        }  
    };  
  
    REP(i, 1LL<<(n-2)) if(dfs(dfs, n, i) == hs) {  
        cout << n << " " << i << "\n";  
        return 0;  
    }  
  
    return 0;  
}