「uoj429」集训队作业2018 串串划分

这个题是一个经典的 runs 题，基本上求出 runs 之后代码就很简单了，第一次做还是想了很久，对着杨主力的代码 memory 了一下，还是勉强懂了，芜湖~

Description

给定一个长度为 $n$ 字符串 $s$，求 $s$ 的一个划分 $t_1,t_2\dots t_k$，满足每个 $t_i$ 都是不循环的，并且 $t_i \ne t_{i + 1}$ 。

Solution

考虑第二个限制，如果我们把一个循环的串划分成多个相同的串，那么他依然是不满足条件的，于是我们就可以拆开每一个循环串，于是第一个限制就没有了，只要考虑相邻的子串不相同就完事了。

这个东西会比较好算，我们考虑容斥， 枚举相邻的两个子串是否是一样的，假设一共有 $k$ 对相邻的子串相同， 那么对答案的贡献就是 $(-1)^{k}$ ，把这个容斥写进 $dp$ 里，令 $f_i$ 为前 $i$ 个字符划分的答案，有转移

$$\begin{split} f_i = \sum_{j = 1}^{i - 1}f_{j}\cdot (-1)^{S(j +1, i) - 1} \end{split}$$

其中 $S(l, r)$ 表示 $s[l, r]$ 这个字符串是由最小循环节循环了几次构成的，比如 $abababab$ 的 $S$ 值为 $4$ ，$1919$ 的 $S$ 值为 2，$114514$ 的 $S$ 值为 $1$ 。

然后我们把这个式子改一下，

$$\begin{split} f_i = \left(\sum_{j=1}^{i-1}f_j\right) + \left(\sum_{j = 1}^{i - 1}f_j\cdot\left[(-1)^{S(j +1, i) - 1} - 1\right]\right) \end{split}$$

前半部分前缀和搞一搞，后半部分 $S(l, r)$ 为奇数时贡献为 $0$ ，只有 $S(l, r)$ 为偶数才有贡献。于是我们就可以把 runs 跑出来，预处理每个循环个数为偶数的循环串然后转移，复杂度会优秀一些。

但是这样还是过不了的，因为循环个数为偶数的串是在是太多了。但是对于一个循环次数为 $2k$ 的循环串，他的右端点为 $r$ ，那么对于 $r$ 这个右端点，必然会有若干个循环串右端点也是 $r$，其循环长度为 $2k, 2(k - 1), 2(k - 2)\dots 2$ （就是每次砍 掉2个） ，那么前面的 $f$ 对他的转移也就是 $f[i-2kl] + f[i - 2(k - 1)l] + f[i - 2(k - 2)l] \dots f[i-2l]$ （l为循环节的长度） 这个东西可以用前缀和优化，转移复杂度为 $O(1)$。也就是说，我们对于一个循环次数极大的循环串，我们可以把比它小的串一起做。对于一个 runs ，样串的个数是 $2p$ ，其中 $p$ 是 runs 的最小循环节。又因为每个 runs 的最小循环节的两倍唯一对应一个本源平方串，所以这样的串的数量也就等于本源平方串的数量，也就是 $O(n\log{n})$。于是总体转移的复杂度也是 $O(n\log{n})$ 了。

Code

#include <map>
#include <set>
#include <ctime>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <bitset>
#include <cstdio>
#include <cctype>
#include <string>
#include <numeric>
#include <cstring>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std ;
#define int long long
#define rep(i, a, b) for (ll i = (a); i <= (b); ++i)
#define per(i, a, b) for (ll i = (a); i >= (b); --i)
#define loop(it, v) for (auto it = v.begin(); it != v.end(); it++)
#define cont(i, x) for (ll i = head[x]; i; i = edge[i].nex)
#define clr(a) memset(a, 0, sizeof(a))
#define ass(a, cnt) memset(a, cnt, sizeof(a))
#define cop(a, b) memcpy(a, b, sizeof(a))
#define lowbit(x) (x & -x)
#define all(x) x.begin(), x.end()
#define SC(t, x) static_cast <t> (x)
#define ub upper_bound
#define lb lower_bound
#define pqueue priority_queue
#define mp make_pair
#define pb push_back
#define pof pop_front
#define pob pop_back
#define fi first
#define se second
#define y1 y1_
#define Pi acos(-1.0)
#define iv inline void
#define enter putchar('\n')
#define siz(x) ((ll)x.size())
#define file(x) freopen(x".in", "r", stdin),freopen(x".out", "w", stdout)
typedef double db ;
typedef long long ll ;
typedef unsigned long long ull ;
typedef pair <ll, ll> pii ;
typedef vector <ll> vi ;
typedef vector <pii> vii ;
typedef queue <ll> qi ;
typedef queue <pii> qii ;
typedef set <ll> si ;
typedef map <ll, ll> mii ;
typedef map <string, ll> msi ;
const ll maxn = 4e6 + 100 ;
const ll inf = 0x3f3f3f3f ;
const ll iinf = 1 << 30 ;
const ll linf = 2e18 ;
const ll mod = 998244353;
const double eps = 1e-7 ;
template <class T = ll> T chmin(T &a, T b) { return a = min(a, b);}
template <class T = ll> T chmax(T &a, T b) { return a = max(a, b);}
template <class T = ll> T read()
{
    T f = 1, a = 0;
    char ch = getchar() ;
    while (!isdigit(ch)) { if (ch == '-') f = -1 ; ch = getchar() ; }
    while (isdigit(ch)) { a =  (a << 3) + (a << 1) + ch - '0' ; ch = getchar() ; }
    return a * f ;
}

char s[maxn];

ll n, q;

ll sa[maxn], rk[maxn], x[maxn], y[maxn], c[maxn];

void get_sa()
{
    ll m = 114514;
    rep(i, 1, m) c[i] = 0;
    rep(i, 1, n) c[x[i] = s[i]] ++;
    rep(i, 1, m) c[i] += c[i - 1];
    per(i, n, 1) sa[c[x[i]] --] = i;
    for(ll k = 1; k <= n; k <<= 1)
    {
        ll num = 0;
        rep(i, n - k + 1, n) y[++ num] = i;
        rep(i, 1, n) if(sa[i] > k) y[++ num] = sa[i] - k;
        rep(i, 1, m) c[i] = 0;
        rep(i, 1, n) c[x[i]] ++;
        rep(i, 1, m) c[i] += c[i - 1];
        per(i, n, 1) sa[c[x[y[i]]] --] = y[i], y[i] = 0;
        swap(x, y);
        num = x[sa[1]] = 1;
        rep(i, 2, n) x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++ num;
        if(num == n) break ;
        m = num;
    }
    rep(i, 1, n) rk[sa[i]] = i;
}

ll h[maxn];

void get_height(char *s, ll n)
{
    ll pos = 0;
    rep(i, 1, n)
    {
        if(pos) pos --;
        while(s[i + pos] == s[sa[rk[i] - 1] + pos]) pos ++;
        h[rk[i]] = pos;
    }
}


ll st[maxn][21], lg[maxn];

void st_init()
{
    rep(i, 1, n) st[i][0] = h[i];
    rep(j, 1, 20) rep(i, 1, n) st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
    ll tmp = 0;
    rep(i, 1, n)
    {
        if((1 << (tmp + 1)) < i) tmp ++;
        lg[i] = tmp;
    }
}

ll query_lcp(ll l, ll r)
{
    ll len = r - l + 1;
    return min(st[l][lg[len]], st[r - (1 << lg[len]) + 1][lg[len]]);
}

ll get_lcp(ll l, ll r)
{
    l = rk[l], r = rk[r];
    if(l > r) swap(l, r);
    return query_lcp(l + 1, r);
}

ll lyd[2][maxn];

ll sta[maxn], top;

void get_lyd()
{
    rep(i, 1, n)
    {
        while(top && rk[sta[top]] > rk[i]) lyd[0][sta[top]] = i - 1, top --;
        sta[++ top] = i;
    }
    while(top) lyd[0][sta[top]] = n, top --;
    rep(i, 1, n)
    {
        while(top && (n - rk[sta[top]]) > (n - rk[i]))
        {
            ll lcp = query_lcp(rk[sta[top]] + 1, rk[i]);
            // printf("query_lcp : %lld %lld %lld\n", sta[top], i, lcp);
            if(lcp == n - i + 1) break;
            lyd[1][sta[top]] = i - 1, top --;
        }
        sta[++ top] = i;
    }
    while(top) lyd[1][sta[top]] = n, top --;
}

ll tot, cnt;

ll vis[maxn];

pair <pii, ll> runs[maxn], tmp[maxn];

void get_runs()
{
    rep(k, 0, 1)
    {
        rep(i, 1, n)
        {
            // printf("i : %lld\n", i);
            ll l = i, r = lyd[k][i], len = r - l + 1;
            r = r + get_lcp(r + 1, l);
            ll tl = 1, tr = l - 1;
            while(tl <= tr)
            {
                ll mid = (tl + tr) >> 1;
                ll tmp = i - mid;
                if(get_lcp(mid, lyd[k][i] - tmp + 1) >= tmp) l = mid, tr = mid - 1;
                else tl = mid + 1;
            }
            // printf("%lld : %lld %lld %lld\n", i, l, r, len);
            if(r - l + 1 >= len * 2) runs[++ tot] = mp(mp(l, r), len);
        }
    }
    sort(runs + 1, runs + tot + 1);
    ll lastl = 0, lastr = 0;
    rep(i, 1, tot)
    {
        if(runs[i].fi.fi == lastl && runs[i].fi.se == lastr) ;
        else lastl = runs[i].fi.fi, lastr = runs[i].fi.se, tmp[++ cnt] = runs[i];
    }
    tot = cnt;
    swap(tmp, runs);
}

ll tot3 = 0;

ll pre[maxn], f[maxn], len[maxn];

vi pos[maxn];

void init()
{
    rep(k, 1, tot)
    {
        ll now = 2 * runs[k].se, l = runs[k].fi.fi, r = runs[k].fi.se;
        rep(i, 0, now - 1)
        {
            if(l + i + now - 1 > r) break;
            len[++ tot3] = now;
            for(ll j = l + i + now - 1; j <= r; j += now) pos[j].pb(tot3);
        }
    }
    return ;
}

void solve()
{
    f[0] = 1;
    ll sum = 1;
    rep(i, 1, n)
    {
        (f[i] += sum) %= mod;
        ll cnt = 0;
        for(ll j : pos[i])
        {
            (pre[j] += f[i - len[j]]) %= mod;
            (cnt += pre[j]) %= mod;
        }
        (cnt *= mod - 2) %= mod;
        (f[i] += cnt) %= mod;
        (sum += f[i]) %= mod;
    }
    printf("%lld\n", f[n]);
}

signed main()
{
    // file("main");
    scanf("%s", s + 1), n = strlen(s + 1);
    get_sa(), get_height(s, n), st_init(), get_lyd(), get_runs();

    // rep(i, 1, tot) printf("%lld %lld %lld\n", runs[i].fi.fi, runs[i].fi.se, runs[i].se);

    init(), solve();

    return 0;
}

/*
20 1
baba babababbbbaba baa
5 17

*/