CF*2600，应当是到目前为止做过的题里相当难的一道了。

Solution

前几天刚好做了一道也是斐波那契字符串相关的 CF379D New Year Letter，类似于我那题的题解，打表出拼接字符串出现的次数。

现在需要确定的就是表中的 a 与 b 具体表示的字符串。这里 a 与 b 应当满足不超过 2 次拼接的条件。显然，不超过 2 次拼接这个条件可以通过找到最小的大于询问串串长的斐波那契数列中的数所对应的斐波那契字符串来解决。加粗的这句话读着有点绕，仔细理解一下应该就会做了。

那么就每个询问独立做，每次用 KMP 计算 a、b、ab、ba、bb 中模式串的个数再统计答案。

CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> pi;
inline int gin(){
    int s=0,f=1;
    char c=getchar();
    while(c<'0' || c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        s=(s<<3)+(s<<1)+(c^48);
        c=getchar();
    }
    return s*f;
}

const int mod=1e9+7;
int n,m,k,t,fib[32],fail[1000005];
string f[32];
char s[100005];
map<string,int> mp;

pi Fib(int n) {
    if(n< 0) return {0,0};
    if(n==0) return {0,1};
    pi p=Fib(n>>1);
    int c=p.first*((2*p.second-p.first+mod)%mod)%mod;
    int d=(p.first*p.first+p.second*p.second)%mod;
    if(n&1) return {d,c+d};
    else return {c,d};
}

inline void pre() {
    fail[1]=0;
    int j=0;
    for(int i=1;i<n;i++){
        while(j && s[j+1]!=s[i+1]) j=fail[j];
        if(s[j+1]==s[i+1]) j++;
        fail[i+1]=j;
    }
}

inline int kmp(string S) {
    int len=S.size();
    S=" "+S;
    int j=0,res=0;
    for(int i=0;i<len;i++) {
        while(j && s[j+1]!=S[i+1]) j=fail[j];
        if(s[j+1]==S[i+1]) j++;
        if(j==n) {
            res=(res+1)%mod;
            j=fail[j];
        }
    }
    return res%mod;
}

signed main(){
    // freopen("test.in","r",stdin);
    // freopen("test.out","w",stdout);
    fib[0]=0,fib[1]=1,f[1]="a",f[2]="b";
    for(int i=2;i<=31;i++) fib[i]=fib[i-1]+fib[i-2];
    for(int i=3;i<=31;i++) f[i]=f[i-1]+f[i-2];
    k=gin(),m=gin();
    if(k==1) {
        while(m--) {
            scanf("%s",s+1);
            if(s[1]=='a' && s[2]==0) puts("1");
            else puts("0");
        }
        return 0;
    }
    if(k==2) {
        while(m--) {
            scanf("%s",s+1);
            if(s[1]=='b' && s[2]==0) puts("1");
            else puts("0");
        }
        return 0;
    }
    while(m--) {
        scanf("%s",s+1);
        if(mp[s+1]) {
            printf("%I64d\n",mp[s+1]);
            continue;
        }
        n=strlen(s+1);
        pre();
        for(int i=2;i<=31;i++) if(fib[i]>n) {t=i; break;}
        if(t>=k) {
            printf("%I64d\n",kmp(f[k]));
            continue;
        }
        // if(t-1>k) {puts("0"); continue;}
        // else t--;
        // if(t>2) t--;
        // else t=1;
        string s1=f[t],s2=f[t+1];
        int a=kmp(s1),b=kmp(s2),ab=(kmp(s1+s2)-a-b+mod)%mod,ba=(kmp(s2+s1)-a-b+mod)%mod,bb=(kmp(s2+s2)-b-b+mod)%mod;
        int A=Fib(k-2-t+1).first,B=Fib(k-1-t+1).first;
        int AB=Fib(k-2-t+1).first+(((k-2-t+1>0) && (k-2-t+1)&1)?-1:0);
        int BA=A;
        int BB=Fib(k-3-t+1).first+(((k-3-t+1>0) && (k-3-t+1)&1)?-1:0);
        // printf("$ %lld $ \n",t);
        // cout<<s1<<" "<<s2<<" "<<s1+s2<<" "<<s2+s1<<" "<<s2+s2<<"\n";
        // printf("& %lld %lld %lld %lld %lld\n",a,b,ab,ba,bb);
        // printf("# %lld %lld %lld %lld %lld\n",A,B,AB,BA,BB);
        int ans=((a*A%mod+b*B%mod)%mod+(ab*AB%mod+ba*BA%mod)%mod+bb*BB%mod)%mod;
        mp[s+1]=ans;
        printf("%I64d\n",ans);
    }
    return 0;
}