[JZOJ4467][JSOI2016?]無界單詞

題目大意

一個長度為 n ，隻含有a和 b 兩種字元的字元串。一個串為無界單詞當且僅當，該串不存在長度小于n的相同前字尾（ ∀0<i<n ， s0..i−1≠sn−i..n−1 ），否則為有界單詞。

要求解答兩個問題：

∙ 共有多少個長度為 n 的無界單詞

∙排名第 k 的無界單詞是什麼（保證第k名存在）

一個資料點共有 T 個測試資料。

1≤n≤64,1≤T≤5

題目分析

首先我們可以求出有界單詞，然後用總數減一減得到無界單詞。

為了避免重複計算，我們考慮如何表達一個有界單詞？可以發現一個有界單詞一定為字首和字尾為某一無界單詞，中間填上一些其它字元，而且這個無界單詞是唯一的，且長度不會超過原串一半。

那麼現在第一問的解決就顯然了。

為了适應c++的數組下标，一下遞推方程采用從 0 編号的順序。

令fi表示枚舉到第 i 位（長度為i+1）的串的無界單詞個數。

顯然可得

fi=2i+1−∑j=02(j+1)≤i+1fj×2i−2j−1

現在考慮如何求解第二個詢問，考慮我們目前已經得到長度為 len 的串，那麼我們要計算采用這種串作為字首的無界單詞個數。

令 gi 表示枚舉到第 i 位（長度為i+1）且使用該串作為字首的無界單詞個數，分情況讨論：

• i<len

  直接判斷已知串前 i+1 位是否是無界單詞即可

否則依然使用 2i+1−len 減去有界單詞個數，枚舉 j 表示考慮字首[0..j)作為無界單詞的有界單詞，将問題轉化為求有界單詞個數：

• len×2≤i+1
  • j<len ：該位對 fi 的貢獻為 fj×2i−2j−1
  • j≤len ：該位對 fi 的貢獻為 fj×2i−j−len
• len×2>i+1
  • i−j<len ：該位對 fi 的貢獻為 fj×2i−j−len
  • i−j≤len ：此時我們選取的部分作為字尾的時候會和已知串的後面某些位置重疊，是以我們要使用哈希、 KMP 預處理或者暴力等方法判斷一下子串 [0,len−i+j) 與子串 [i−j,len) 是否相同，相同則貢獻為 1 。

那麼我們直接遞歸每一位，先填上a，然後計算無界單詞個數，如果大于等于 k 就遞歸下去，否則該位填b且 k 減去無界單詞個數。

時間複雜度為O(Tn3)或 O(Tn4) ，取決于你使用什麼判斷最後一種情況。

代碼實作

#include <iostream>
#include <cstdio>

using namespace std;

typedef long long LL;

const int N=;

LL f[N],pw[N];
char c[]={'a','b'};
bool s[N];
int n,T;
int p[N];
LL K;

void pre()
{
    pw[]=;
    for (int i=;i<N-;i++)
        pw[i]=pw[i-]*;
}

void clear()
{
    for (int i=;i<n;i++)
        f[i]=;
}

void calcall()
{
    clear();
    f[]=;
    for (int i=;i<n;i++)
    {
        for (int j=;(j+)*<=i+;j++)
            f[i]+=f[j]*pw[i-j*-];
        f[i]=pw[i+]-f[i];
    }
}

void kmp(int len)
{
    p[]=;
        int cur=;
        for (int i=;i<len;i++)
        {
                while (cur&&s[cur]!=s[i])
                        cur=p[cur-];
                if (s[cur]==s[i])
                        cur++;
                p[i]=cur;
        }
}

bool same(int st0,int en0,int st1)
{
    for (int i=;st0+i<=en0;i++)
        if (s[i+st0]!=s[i+st1])
            return false;
    return true;
}

LL calc(int len)
{
    clear();
    kmp(len);
    for (int i=;i<n;i++)
        if (i<len)
            f[i]=p[i]==;
        else
        {
            for (int j=;(j+)*<=i+;j++)
                if (len*<=i+&&j>=len)
                    f[i]+=f[j]*pw[i-j*-];
                else
                    if (len<=i-j)
                        f[i]+=f[j]*pw[i-j-len];
                    else
                        if (same(i-j,len-,))
                            f[i]+=f[j];
            f[i]=pw[i+-len]-f[i];
        }
    return f[n-];
}

void find(int cur,LL rank)
{
    if (cur==n)
        return;
    s[cur]=;
    LL sum=calc(cur+);
    if (sum>=rank)
    {
        find(cur+,rank);
        return;
    }
    s[cur]=;
    find(cur+,rank-sum);
}

int main()
{
    pre();
    freopen("word.in","r",stdin);
    freopen("word.out","w",stdout);
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d %lld",&n,&K);
        calcall();
        printf("%lld\n",f[n-]);
        find(,K);
        for (int i=;i<n;i++)
            putchar(c[s[i]]);
        putchar('\n');
    }
    fclose(stdin);
    fclose(stdout);
    return ;
}