# Codeforces Round #393 (Div. 1) (8VC Venture Cup 2017 - Final Round Div. 1 Edition): D. Bacterial Melee

,

http://codeforces.com/contest/759/problem/D

## note

• 「$i$文字目を最後に使った」ではなく「文字$c$を最後に使った」で状態を圧縮するのはだめな方針
• segment木の操作を雑にやるとTLE
• 文字種$L = 26$が乗って$O(L n^2 \log n)$なものは間に合わなかった
• kmjpさんの解説を読んだ: http://kmjp.hatenablog.jp/entry/2017/01/27/0930

## implementation

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < int(n); ++ (i))
#define REP_R(i, n) for (int i = int(n) - 1; (i) >= 0; -- (i))
#define ALL(x) begin(x), end(x)
using ll = long long;
using namespace std;

template <class Monoid>
struct segment_tree {
typedef typename Monoid::underlying_type underlying_type;
int n;
vector<underlying_type> a;
Monoid mon;
segment_tree() = default;
segment_tree(int a_n, underlying_type initial_value = Monoid().unit(), Monoid const & a_mon = Monoid()) : mon(a_mon) {
n = 1; while (n < a_n) n *= 2;
a.resize(2 * n - 1, mon.unit());
fill(a.begin() + (n - 1), a.begin() + ((n - 1) + a_n), initial_value); // set initial values
REP_R (i, n - 1) a[i] = mon.append(a[2 * i + 1], a[2 * i + 2]); // propagate initial values
}
void point_set(int i, underlying_type z) { // 0-based
a[i + n - 1] = z;
for (i = (i + n) / 2; i > 0; i /= 2) { // 1-based
a[i - 1] = mon.append(a[2 * i - 1], a[2 * i]);
}
}
underlying_type range_concat(int l, int r) { // 0-based, [l, r)
underlying_type lacc = mon.unit(), racc = mon.unit();
for (l += n, r += n; l < r; l /= 2, r /= 2) { // 1-based loop, 2x faster than recursion
if (l % 2 == 1) lacc = mon.append(lacc, a[(l ++) - 1]);
if (r % 2 == 1) racc = mon.append(a[(-- r) - 1], racc);
}
return mon.append(lacc, racc);
}
// fast methods
inline underlying_type point_get(int i) {
return a[i + n - 1];
}
inline void point_set_primitive(int i, underlying_type z) {
a[i + n - 1] = z;
}
void point_set_commit() {
REP_R (i, n - 1) a[i] = mon.append(a[2 * i + 1], a[2 * i + 2]);
}
};
struct plus_monoid {
typedef ll underlying_type;
ll unit() const { return 0; }
ll append(ll a, ll b) const { return a + b; }
};

constexpr int MOD = 1e9 + 7;
int solve(int n, string const & s) {
typedef segment_tree<plus_monoid> segtree;
segtree cur(n + 1);
cur.point_set(0, 1);
REP (j, n) {
segtree prv = cur;
cur = segtree(n + 1);
array<int, 26> last;
fill(ALL(last), -1);
REP (i, n) {
int c = s[i] - 'a';
ll v1 = prv.range_concat(last[c] + 1, i);
ll v2 = prv.point_get(i);
cur.point_set_primitive(i, (v1 + v2) % MOD);
last[c] = i;
}
cur.point_set_commit();
}
return (cur.range_concat(0, n + 1) % MOD + MOD) % MOD;
}

int main() {
int n; cin >> n;
string s; cin >> s;