Revolving Digits

题面

【题目描述】：

有一天，Silence对可以旋转的正整数十分感兴趣。在旋转操作中，他可以把后面的数字按照原位置不动地搬到剩下位置的前面。当然，他也可以完全不动这串数字。比如，他可以把123变为123，231,312三种。现在他想知道他能得到多少个不同的整数，但他又觉得这个问题太简单了，所以开始思考这所有的整数中有多少个比原数大，有多少个比原数小，又有多少个和原数相等。我们将保证原来的整数是正的，它没有前导0，但如果我们通过旋转得到一个带前导0的数字，我们忽略它的前导0,比如，104旋转后能变成041，我们将它看为41。

【输入描述】：

输入的第一行包含一个整数t(1<=t<=50)，这意味着测试数据的组数。

对于每组数据，只有一行包含一个整数n(n<=10^100000)，我们将确保n是一个没有前导0的正整数。

【输出描述】：

对于每组数据，请输出一行包括三个整数，输出格式为"Case X: L E G"（不包含双引号）,X表示当前数据的组数。L表示通过旋转操作比n小的数字的个数。E表示通过旋转过后等于n的数字的个数。G表示通过旋转操作比n大的数字的个数。

【输入样例】：

1

341

【输出样例】：

Case 1: 1 1 1

题解

首先, 注意到题目要求的整数是"不相同"的, 因此要把原数进行KMP去完整循环节.

然后跑一次扩展KMP, \(match[i]\)表示可以匹配的最大长度, 因此说明

\(match[i] +1\)位是不匹配的, 比较这一位即可.

#include <cstdio>

#include <cstring>

#include <algorithm>

const int L = (int)1e5;

int main()

{

    #ifndef ONLINE_JUDGE

    freopen("revolving.in", "r", stdin);

    #endif

    int t;

    scanf("%d", &t);

    for(int cs = 1; cs <= t; ++ cs)

    {

        static char str[L <<1];

        scanf("%s", str);

        int len = strlen(str);

        static int nxt[L];

        nxt[0] = -1;

        int p = nxt[0];

        for(int i = 1; i < len; ++ i)

        {

            for(; ~ p && str[p + 1] ^ str[i]; p = nxt[p]);

            nxt[i] = str[p + 1] == str[i] ? ++ p : p;

        }

        if(len % (len - nxt[len - 1] - 1) == 0)

            len -= nxt[len - 1] + 1;

        for(int i = 0; i < len; ++ i)

            str[i + len] = str[i];

        static int mtch[L << 1];

        mtch[0] = (len << 1) - 1;

        p = 1;

        mtch[p] = -1;

        for(; p + mtch[p] + 1 < len << 1 && str[mtch[p] + 1] == str[p + mtch[p] + 1]; ++ mtch[p]);

        int mx = p + mtch[p];

        for(int i = 1; i < len << 1; ++ i)

        {

            mtch[i] = std::max(-1, std::min(mx - i, mtch[i - p]));

            for(; i + mtch[i] + 1 < len << 1 && str[mtch[i] + 1] == str[i + mtch[i] + 1]; ++ mtch[i]);

            if(i + mtch[i] > mx)

                p = i, mx = p + mtch[p];

        }

        int L = 0, E = 1, G = 0;

        for(int i = 1; i < len; ++ i)

            if(mtch[i] + 1 >= len)

                ++ E;

            else if(str[i + mtch[i] + 1] > str[mtch[i] + 1])

                ++ G;

            else

                ++ L;

        printf("Case %d: %d %d %d\n", cs, L, E, G);

    }

}

巴特西