CF 7D Palindrome Degree

传送门

思路

  不是马拉车加随便 DP 乱搞？本来想复习一下马拉车的，结果拉出了许多事端（修复了 OI Learner Judge 的严重 bug——一个害我调了两节课的 bug）。唉，最后的原因居然是马拉车没有减一（maxRight 我是写的闭区间），害得我调了这么久的傻逼题。唉，我太弱啦！大家都用哈希过了，太强啦！

  设 fi f i $f_i$ 表示你懂的，如果 0∼i 0 ∼ i $0 \sim i$ 是回文串，那就转移（注意差一错误），否则为 0 0 <script type="math/tex" id="MathJax-Element-41">0</script>。唉这题这么傻逼就自己去想吧，反正我太弱了，马拉车写错了，调了一晚上，唉，我太弱啦！

参考代码

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cassert>
#include <cctype>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <functional>
#define loop register int
typedef long long LL;
typedef unsigned long long ULL;
using std::cin;
using std::cout;
using std::endl;
typedef LL INT_PUT;
INT_PUT readIn()
{
    INT_PUT a = 0; bool positive = true;
    char ch = getchar();
    while (!(ch == '-' || std::isdigit(ch))) ch = getchar();
    if (ch == '-') { positive = false; ch = getchar(); }
    while (std::isdigit(ch)) { a = a * 10 - (ch - '0'); ch = getchar(); }
    return positive ? -a : a;
}
void printOut(INT_PUT x)
{
    char buffer[20]; int length = 0;
    if (x < 0) putchar('-'); else x = -x;
    do buffer[length++] = -(x % 10) + '0'; while (x /= 10);
    do putchar(buffer[--length]); while (length);
    putchar('\n');
}

const int maxn = int(6e6) + 5;

struct Manacher
{
    char str[maxn * 2];
    int length;
    int rl[maxn * 2];
    void init(const char* s)
    {
        str[length++] = '#';
        for (; *s != '\0'; s++)
        {
            str[length++] = *s;
            str[length++] = '#';
        }
    }
    void manacher()
    {
        rl[0] = 1;
        int maxR = 0;
        int center = 0;
        for (loop i = 1; i < length; i++)
        {
            register int cnt;
            if (i <= maxR)
                cnt = std::min(maxR - i + 1, rl[(center << 1) - i]);
            else
                cnt = 1;

            while (i - cnt >= 0 && i + cnt < length &&
                str[i - cnt] == str[i + cnt])
                cnt++;
            if (i + cnt - 1 > maxR) // note: -1!!!
            {
                maxR = i + cnt - 1;
                center = i;
            }
            rl[i] = cnt;
        }
    }
    inline bool judge(int i)
    {
        return rl[i + 1] >= i + 2;
    }
} manacher;

int n;
char str[maxn];
int f[maxn];
inline bool isValid(char ch)
{
    return std::isalpha(ch) || std::isdigit(ch);
}

void run()
{
    char ch = getchar();
    while (!isValid(ch)) ch = getchar();
    while (isValid(ch))
    {
        str[n++] = ch;
        ch = getchar();
    }
    //printOut(n);
    manacher.init(str);
    manacher.manacher();

    register LL ans = 1;
    f[0] = 1;
    for (loop i = 1; i < n; i++)
    {
        if (manacher.judge(i))
            f[i] = f[(i - 1) >> 1] + 1;
        else
            f[i] = 0;
        ans += f[i];
    }
    printOut(ans);
}

int main()
{
    run();
    return 0;
}