[hdu 5351] MZL's Border

題目連結，我怎麼知道題目的标題是什麼意思？

題目大意：

定義字元串 s1=a ， s2=b ， si=si−1+si−2  (i≥3)

同時定義一個字元串 s 的權值為一個最大的 i<|s| 滿足 s 長度為 i 的字首等于長度為 i 的字尾。

比如字元串 aba 的權值就是 1 ，abab 的權值就是 2 ，aaaa 的權值就是 3 。

求 sn 的前 m 個字元組成的字元串的權值，輸出權值取模 258280327 的結果。

首先很顯然的一點是， si 包含 si−1  (i≥3)

那麼我們考慮 n≥3 的情況, 設 fi 表示 sn 的前 i 個字元組成的字元串的權值

然後用 KMP 求出 next 數組得到 {fi}  (n=19) ：

{fi}={0,0,1,1,2,3,2,3,4,5,6,4,5,6,7,8,9,10,11}

将連續的數字分成一段：

0   0 1   1 2 3   2 3 4 5 6   4 5 6 7 8 9 10 11

分成的段的長度分别為 1,2,3,5,8 ，起始值分别為 0,0,1,2,4

可以發現，每一段長度都是 fibi+1 ，起始值都是 fibi−1 ( fibi 為斐波拉契數列 )

大膽猜想，小心假設， 從不證明！

與暴力對拍之後發現這個規律是對的。

考慮 next[] 數組的構造即可證明這個結論。

根據這個規律可以 O(n) 求出答案，然後就做完了

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <vector>
#include <utility>
#include <stack>
#include <queue>
#include <map>
#include <iostream>
#include <algorithm>

template<class Num>void read(Num &x)
{
    char c; int flag = ;
    while((c = getchar()) < '0' || c > '9')
        if(c == '-') flag *= -;
    x = c - '0';
    while((c = getchar()) >= '0' && c <= '9')
        x = (x<<) + (x<<) + (c-'0');
    x *= flag;
    return;
}
template<class Num>void write(Num x)
{
    if(!x) {putchar('0');return;}
    if(x < ) putchar('-'), x = -x;
    static char s[];int sl = ;
    while(x) s[sl++] = x% + '0',x /= ;
    while(sl) putchar(s[--sl]);
}
const int maxn = , maxL = , Base = , Mod = ;
int n;

struct BigNum
{
    int len, num[maxL]; 

    void read()
    {
        static char s[maxL];
        scanf("%s", s + );
        len = strlen(s + );
        for(int i = len; i >= ; i--)
            num[i] = s[len +  - i] - '0';
    }
    void write()
    {
        if(!len)
        {
            putchar('0');
            return;
        }
        for(int i = len; i >= ; i--)
            putchar(num[i] + '0');
    }

}m, F[maxn + ], empty, one, two;

BigNum operator + (const BigNum &a,const BigNum &b)
{
    BigNum c = empty;
    c.len = std::max(a.len, b.len);
    for(int i = ; i <= c.len; i++)
        c.num[i] = a.num[i] + b.num[i];
    for(int i = ; i <= c.len; i++)
    {
        c.num[i + ] += c.num[i] / Base;
        c.num[i] %= Base;
    }
    while(c.num[c.len + ])
    {
        ++c.len;
        c.num[c.len + ] += c.num[c.len] / Base;
        c.num[c.len] %= Base;
    }
    return c;
}
BigNum operator - (const BigNum &a,const BigNum &b)
{
    BigNum c = empty;
    for(int i = ; i <= a.len; i++)
        c.num[i] = a.num[i] - b.num[i];
    for(int i = ; i <= a.len; i++)
    {
        if(c.num[i] < )
        {
            c.num[i + ] --;
            c.num[i] += Base;
        }
    }
    c.len = ;
    for(int i = a.len; i >= ; i --)
    {
        if(c.num[i])
        {
            c.len = i;
            break;
        }
    }
    return c;
}
bool operator > (const BigNum &a,const BigNum &b)
{
    if(a.len != b.len) return a.len > b.len;
    for(int i = a.len; i >= ; i--)
    {
        if(a.num[i] != b.num[i])
            return a.num[i] > b.num[i];
    }
    return false;
}
int operator %(const BigNum &a,int mod)
{
    int r = ;
    for(int i = a.len; i >= ; i--)
        r = ((long long)r * Base + a.num[i])%Mod;
    return r;
}

void prework()
{
    one.num[] = one.len = ;
    two.num[] = , two.len = ;

    F[] = F[] = one;
    for(int i = ; i <= maxn; i++)
        F[i] = F[i - ] + F[i - ];
}
void init()
{
    read(n), m.read();
}
void solve()
{
    for(int i = ; i <= n; i++)
    {
        if(m > F[i])
            m = m - F[i];
        else
        {
            write((F[i - ] + m - two)%Mod);
            puts("");
            return;
        }
    }
}

int main()
{
    int T;

    read(T);
    prework();

    while(T--) init(), solve();

    return ;
}