hihocoder1466 重复旋律9

题目描述

小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一段音乐旋律可以被表示为一段字符构成的字符串。

现在小Hi已经不满足于单单演奏了!他通过向一位造诣很高的前辈请教,通过几周时间学习了创作钢琴曲的基本理论,并开始对曲目做改编或者原创。两个月后,小Hi决定和前辈进行一场创作曲目的较量!

规则是这样的,有两部已知经典的作品,我们称之为A和B。经典之所以成为经典,必有其经典之处。

刚开始,纸上会有一段A的旋律和一段B的旋律。两人较量的方式是轮流操作,每次操作可以选择在纸上其中一段旋律的末尾添加一个音符,并且要求添加完后的旋律依然是所在作品的旋律(也就是A或B的一个子串)。谁词穷了(无法进行操作)就输了。

小Hi和前辈都足够聪明,但是小Hi还是太年轻,前辈打算教训他一顿。前辈表示会和小Hi进行K次较量,只要小Hi赢了哪怕一次就算小Hi获得最终胜利。但是前提是开始纸上的两段旋律需要他定。小Hi欣然同意,并且表示每次较量都让前辈先操作。

前辈老谋深算,显然是有备而来。他已经洞悉了所有先手必胜的初始(两段)旋律。第i天前辈会挑选字典序第i小的初始(两段)旋律来和小Hi较量。那么问题来了,作为吃瓜群众的你想知道,最后一天即第K天,前辈会定哪两个旋律呢?

初始时两段旋律的字典序比较方式是先比较前一个旋律字典序,一样大则比较后一旋律的字典序。

输入格式

第一行包含一个正整数,K。K<=10^18

第二行包含一个非空的仅有小写字母构成的字符串,表示作品A。|A|<=10^5

第三行包含一个非空的仅有小写字母构成的字符串,表示作品B。|B|<=10^5

输出格式

输出共两行,每行一个字符串(可能为空),表示答案。

如果无解则只输出一行"NO"。

样例输入

5
ab
cd

样例输出

a
cd

分析

我们先考虑单串的问题。

一个字符串的子串有$O(n^2)$个,显然不可能一个个枚举。可以发现,按照规则,一个子串对胜负的影响,只与它在原串中的出现位置有关,也就是说出现位置集合相同的子串可以合并到一个状态中。那么自然可以想到建出后缀自动机。

现在考虑如何判断胜负,只需求出每个状态的$sg$函数。因为每个状态的后继状态只有$26$个,可以轻松求出$sg$值,并且所有$sg$值都不会大于$26$。

如果单串的话这题已经做完了,只要找$sg$值不为$0$的第$k$大子串即可。现在考虑两个串的做法,也就是求两串$sg$值不相等的第$k$大。

我们预处理出$B$串中$sg$值不为$x$的子串个数$sumB(x)$,然后在自动机$A$上按字典序$dfs$,每到一个点$u$就把$k$减去$sumB(sg(u))$。最后停下的点即为$A$串的答案,并记录这个点的$sg$值记为$sgA$。

现在只需要在$B$串中找到$sg$值不为$sgA$的第$k$大子串即可,$dfs$一遍就做完了。

另外,找第$k$大时要记得避免重复访问同一个节点,不然复杂度就是$O(n^2)$了。可以用记忆化搜索,也可以先预处理出从状态$u$出发的方案数。

复杂度$O(26n)$。

代码

#include <bits/stdc++.h>
typedef long long ll;

const int N = 1e5+50;
const int SZ = N << 1;

struct Sam {
    int top, last;
    int ch[SZ][26], fa[SZ], mx[SZ];
    int buc[N], tpx[SZ];
    int sg[SZ], siz[SZ];

    Sam(): top(1), last(1) {}

    void extend(char c) {
        int x = c - 'a';
        int p = last, np = last = ++top;
        mx[np] = mx[p] + 1;
        for (; p && !ch[p][x]; p = fa[p])
            ch[p][x] = np;
        if (!p) {
            fa[np] = 1;
            return;
        }
        int q = ch[p][x];
        if (mx[q] == mx[p] + 1) {
            fa[np] = q;
            return;
        }
        int nq = ++top;
        mx[nq] = mx[p] + 1;
        fa[nq] = fa[q];
        fa[q] = fa[np] = nq;
        memcpy(ch[nq], ch[q], sizeof ch[nq]);
        for (; ch[p][x] == q; p = fa[p])
            ch[p][x] = nq;
    }

    void sort() {
        for (int i = 1; i <= top; i++)
            buc[mx[i]]++;
        for (int i = 1; i <= mx[last]; i++)
            buc[i] += buc[i-1];
        for (int i = 1; i <= top; i++)
            tpx[buc[mx[i]]--] = i;
    }

    void init() {
        sort();
        bool vis[27];
        for (int i = top; i >= 1; i--) {
            int u = tpx[i];
            siz[u] = mx[u] - mx[fa[u]];
            for (int j = 0; j <= 26; j++)
                vis[j] = false;
            for (int x = 0; x < 26; x++) {
                int v = ch[u][x];
                if (!v) continue;
                vis[sg[v]] = true;
            }
            for (int j = 0; j <= 26; j++) {
                if (!vis[j]) {
                    sg[u] = j;
                    break;
                }
            }
        }
        siz[1] = 1;
    }
} sa, sb;

ll k;
char a[N], b[N];
int la, lb;
ll sumB[27];
std::string ansA, ansB;
int sgA;
ll s1[SZ], s2[SZ];
bool foundA, foundB;

void initSumB() {
    for (int i = 1; i <= sb.top; i++) {
        int u = sb.tpx[i];
        for (int j = 0; j <= 26; j++) {
            if (j == sb.sg[u]) continue;
            sumB[j] += sb.siz[u];
        }
    }
}

void initS1() {
    for (int i = sa.top; i >= 1; i--) {
        int u = sa.tpx[i];
        s1[u] = sumB[sa.sg[u]];
        for (int x = 0; x < 26; x++)
            s1[u] += s1[sa.ch[u][x]];
    }
}

void initS2() {
    for (int i = sb.top; i >= 1; i--) {
        int u = sb.tpx[i];
        s2[u] = (sb.sg[u] != sgA);
        for (int x = 0; x < 26; x++)
            s2[u] += s2[sb.ch[u][x]];
    }
}

void dfsA(int u) {
    ll cur = sumB[sa.sg[u]];
    if (k <= cur) {
        sgA = sa.sg[u];
        foundA = true;
        return;
    }
    k -= cur;
    for (int x = 0; x < 26; x++) {
        int v = sa.ch[u][x];
        if (!v) continue;
        if (k > s1[v]) {
            k -= s1[v];
            continue;
        }
        ansA += 'a' + x;
        dfsA(v);
        return;
    }
}

void dfsB(int u) {
    ll cur = (sb.sg[u] != sgA);
    if (k <= cur) {
        foundB = true;
        return;
    }
    k -= cur;
    for (int x = 0; x < 26; x++) {
        int v = sb.ch[u][x];
        if (!v) continue;
        if (k > s2[v]) {
            k -= s2[v];
            continue;
        }
        ansB += 'a' + x;
        dfsB(v);
        return;
    }
}

int main() {
    scanf("%lld%s%s", &k, a+1, b+1);
    la = strlen(a+1);
    lb = strlen(b+1);
    for (int i = 1; i <= la; i++)
        sa.extend(a[i]);
    for (int i = 1; i <= lb; i++)
        sb.extend(b[i]);
    sa.init();
    sb.init();

    initSumB();
    initS1();
    dfsA(1);
    if (!foundA) {
        puts("NO");
        return 0;
    }

    initS2();
    dfsB(1);
    if (!foundB) {
        puts("NO");
        return 0;
    }

    std::cout << ansA << std::endl << ansB << std::endl;
    return 0;
}


转载请注明出处。


评论列表,共 0 条评论

    暂无评论

发表评论