p232.ans1
======================
914

=================
p232.ans2
======================
75

=================
p232.ans3
======================
0000

=================
p232.cpp
======================
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n, k;
vector<int> d;

void read() {
    cin >> n >> k;
    string s;
    cin >> s;

    d.resize(n);
    for(int i = 0; i < n; i++) {
        d[i] = s[i] - '0';
    }
}

template<typename T>
int least_rotation(const vector<T>& s) {
    int n = s.size();
    if(n == 0) {
        return 0;
    }

    vector<int> f(2 * n, -1);
    int k_ = 0;
    for(int j = 1; j < 2 * n; ++j) {
        int i = f[j - k_ - 1];
        while(i != -1 && s[j % n] != s[(k_ + i + 1) % n]) {
            if(s[j % n] < s[(k_ + i + 1) % n]) {
                k_ = j - i - 1;
            }
            i = f[i];
        }

        if(i == -1 && s[j % n] != s[(k_ + i + 1) % n]) {
            if(s[j % n] < s[(k_ + i + 1) % n]) {
                k_ = j;
            }
            f[j - k_] = -1;
        } else {
            f[j - k_] = i + 1;
        }
    }

    return k_;
}

template<typename T>
vector<T> max_cyclic_shift(const vector<T>& v) {
    if(v.empty()) {
        return {};
    }

    int m = v.size();
    vector<T> t(m);
    for(int i = 0; i < m; i++) {
        t[i] = -v[i];
    }

    int kk = least_rotation(t);
    vector<T> ans(m);
    for(int i = 0; i < m; ++i) {
        ans[i] = v[(kk + i) % m];
    }

    return ans;
}

void solve() {
    // Following index i by repeated +K mod N visits a cycle of the permutation;
    // the infinite fraction starting at any index of that cycle is periodic with
    // that cycle as its period. Two starts on the same cycle differ only by a
    // rotation of the period, so the largest fraction from a cycle corresponds
    // to its lexicographically maximum cyclic shift (found via Booth's least-
    // rotation algorithm on the negated digits). We take the best shift over all
    // cycles, then print the first N digits by repeating the winning period.

    vector<bool> used(n, false);
    vector<int8_t> ans;
    for(int i = 0; i < n; i++) {
        if(used[i]) {
            continue;
        }

        vector<int8_t> cycle;
        for(int j = i; !used[j]; j = (j + k) % n) {
            used[j] = true;
            cycle.push_back(d[j]);
        }

        cycle = max_cyclic_shift(cycle);
        if(ans.empty() || cycle > ans) {
            ans = cycle;
        }
    }

    for(int i = 0; i < n; i++) {
        cout << (int)ans[i % ans.size()];
    }

    cout << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}

=================
p232.in1
======================
3 2
194

=================
p232.in2
======================
2 1
57

=================
p232.in3
======================
4 1
0000

=================
p232_suffix_automaton.cpp
======================
#include <bits/stdc++.h>
// #include <coding_library/strings/suffix_automaton.hpp>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

template<class T = string>
class SuffixAutomaton {
  private:
    using G = conditional_t<
        is_same_v<T, const char*> || is_same_v<T, char*> || is_array_v<T>, char,
        typename T::value_type>;

    struct State {
        map<G, int> to;
        int len;
        int link;
        State(int l = 0, int lnk = -1) : len(l), link(lnk) {}
    };

    int check_replace_with_clone(int p, G c) {
        int q = states[p].to[c];
        if(states[p].len + 1 == states[q].len) {
            return q;
        }

        int clone = states.size();
        states.emplace_back(states[p].len + 1, states[q].link);
        states[clone].to = states[q].to;
        while(p >= 0 && states[p].to[c] == q) {
            states[p].to[c] = clone;
            p = states[p].link;
        }
        states[q].link = clone;
        return clone;
    }

  public:
    int last;
    vector<State> states;

    SuffixAutomaton() : last(0) { clear(); }
    SuffixAutomaton(const T& s) { init(s); }

    void add_letter(G c) {
        if(states[last].to.count(c)) {
            int clone = check_replace_with_clone(last, c);
            last = clone;
            return;
        }

        int p = last;
        last = states.size();
        states.emplace_back(states[p].len + 1);

        while(p >= 0 && !states[p].to.count(c)) {
            states[p].to[c] = last;
            p = states[p].link;
        }

        if(p == -1) {
            states[last].link = 0;
            return;
        }

        int q_or_clone = check_replace_with_clone(p, c);
        states[last].link = q_or_clone;
    }

    void add_string(const T& s) {
        last = 0;
        for(char c: s) {
            add_letter(c);
        }
    }

    void clear() {
        states.clear();
        states.emplace_back();
        last = 0;
    }

    void init(const T& s) {
        clear();
        add_string(s);
    }

    vector<vector<int>> build_suffix_link_tree() {
        vector<vector<int>> adj(states.size());
        for(int i = 1; i < (int)states.size(); i++) {
            adj[states[i].link].push_back(i);
        }
        return adj;
    }
};

int n, k;
vector<int> d;

void read() {
    cin >> n >> k;
    string s;
    cin >> s;

    d.resize(n);
    for(int i = 0; i < n; i++) {
        d[i] = s[i] - '0';
    }
}

template<typename T>
vector<T> max_cyclic_shift(const vector<T>& v) {
    static SuffixAutomaton<vector<int>> sa = SuffixAutomaton<vector<int>>();
    sa.clear();
    for(int i = 0; i < (int)v.size(); i++) {
        sa.add_letter(v[i]);
    }
    for(int i = 0; i < (int)v.size(); i++) {
        sa.add_letter(v[i]);
    }

    vector<int> dp(sa.states.size(), -1);
    function<void(int)> dfs = [&](int v) {
        if(dp[v] != -1) {
            return;
        }

        dp[v] = 0;
        for(auto [_, u]: sa.states[v].to) {
            dfs(u);
            dp[v] = max(dp[v], 1 + dp[u]);
        }
    };

    for(int i = 0; i < (int)sa.states.size(); i++) {
        dfs(i);
    }

    int u = 0, need = n;
    vector<T> ans;
    while(need > 0) {
        int best_transition = -1;
        for(auto [c, v]: sa.states[u].to) {
            if(dp[v] + 1 >= need) {
                best_transition = max(best_transition, c);
            }
        }
        assert(best_transition != -1);
        ans.push_back(best_transition);
        u = sa.states[u].to[best_transition];
        need--;
    }

    return ans;
}

void solve() {
    vector<bool> used(n, false);
    vector<int8_t> ans;
    for(int i = 0; i < n; i++) {
        if(used[i]) {
            continue;
        }

        int pos = 0;
        vector<int8_t> cycle;
        for(int j = i; !used[j]; j = (j + k) % n) {
            used[j] = true;
            cycle.push_back(d[j]);
            pos++;
        }

        cycle = max_cyclic_shift(cycle);
        if(ans.empty() || cycle > ans) {
            ans = cycle;
        }
    }

    for(int i = 0; i < n; i++) {
        cout << (int)ans[i % ans.size()];
    }

    cout << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}

=================
statement.txt
======================
232. Infinite Fraction
time limit per test: 0.25 sec.
memory limit per test: 4096 KB
input: standard
output: standard



You are given integer numbers N and K and an array D[0..N-1] of decimal digits (0<=D[i]<=9, D[i] is an integer).
Consider an array A of real numbers, such that integer part of A[i] is equal to zero, and fractional part is an infinite decimal fraction with digits D[[(i + 0K) mod N], D[(i + 1K) mod N], D[(i + 2K) mod N] and so on.
For example, for N = 3, K = 2 and D = '194':

A[1] = 0.1491491491...
A[2] = 0.9149149149...
A[3] = 0.4914914914...

You are to find an element of array A with the greatest value and output first N digits of its fractional part.

Input
The first line contains integer numbers N and K (1<=N<=150000; 0<=K<=10^9). The second line contains an array of digits D, given without spaces.

Output
You are to output exactly N characters to the output file, according to the task.

Sample test(s)

Input
Test #1
3 2
194

Test #2
2 1
57

Test #3
4 1
0000

Output
Test #1
914

Test #2
75

Test #3
0000

=================
