读完题感觉分类讨论太多了，想借鉴一下题解，然而并没有题解。于是肝完大讨论之后来写篇题解。

显然，最终的 AC 串的个数由这么几种情况构成：

  1. 初始的串 $s1$ 。
  2. 初始的串 $s2$ 。
  3. $s1$ 与 $s2$ 拼接处 。
  4. $s2$ 与 $s1$ 拼接处 。
  5. $s1$ 与 $s1$ 拼接处 。
  6. $s2$ 与 $s2$ 拼接处 。

上述的前两种情况显然是斐波那契数列中的某一项。

打表推敲一下，发现后四种情况也一定可以用斐波那契数列中的某一项通过代数运算得到。

具体的，图中表格 F 和 G 这两列都可以用 OEIS A052952 计算。

已知了这些东西，结合此题非常小的数据范围，就可以直接枚举两个初始串的 AC 串个数以及每一种拼接情况求解了。

贴一下我的代码吧，不过调错的时候越写越玄学。建议自己当做大模拟来写。

提交记录

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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#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;
}

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

signed main(){
    // freopen("test.in","r",stdin);
    // freopen("test.out","w",stdout);
    int k=gin()-2,x=gin(),n=gin(),m=gin();
    int A=Fib(k).first,B=Fib(k+1).first,AB=A,BA=Fib(k).first-(1+((k&1)?1:-1))/2,BB=Fib(k-1).first-(1-((k&1)?1:-1))/2;
    // cout<<A<<" "<<B<<" "<<AB<<" "<<BA<<" "<<BB<<"\n";
    for(int a=0;a<=n/2;a++) {
        if(a*A>x) continue;
        if(a*A==x) {
            string s1,s2;
            for(int i=1;i<=a;i++) s1+="AC";
            for(int i=1;i<=n-2*a;i++) s1+="B";
            for(int i=1;i<=m;i++) s2+="B";
            printf("%s\n%s\n",s1.c_str(),s2.c_str());
            return 0;
        }
        for(int b=0;b<=m/2;b++) {
            if(b*B==x) {
                string s1,s2;
                for(int i=1;i<=n;i++) s1+="B";
                for(int i=1;i<=b;i++) s2+="AC";
                for(int i=1;i<=m-2*b;i++) s2+="B";
                printf("%s\n%s\n",s1.c_str(),s2.c_str());
                return 0;
            }
            if(a*A+b*B>x) continue;
            if(a*A+b*B==x) {
                string s1,s2;
                for(int i=1;i<=a;i++) s1+="AC";
                for(int i=2*a+1;i<=n;i++) s1+="B";
                for(int i=1;i<=b;i++) s2+="AC";
                for(int i=2*b+1;i<=m;i++) s2+="B";
                printf("%s\n%s\n",s1.c_str(),s2.c_str());
                return 0;
            }
            if(n&1 || a<n/2) {
                if(m&1 || b<m/2) {
                    // s1开头留C s2结尾留A
                    if(a*A+b*B+BA==x) {
                        string s1,s2;
                        for(int i=1;i<=n-2*a;i++) s1+="C";
                        for(int i=1;i<=a;i++) s1+="AC";
                        for(int i=1;i<=b;i++) s2+="AC";
                        for(int i=1;i<=m-2*b;i++) s2+="A";
                        printf("%s\n%s\n",s1.c_str(),s2.c_str());
                        return 0;
                    }
                    // s1结尾留A s2开头留C
                    if(a*A+b*B+AB==x) {
                        string s1,s2;
                        for(int i=1;i<=a;i++) s1+="AC";
                        for(int i=1;i<=n-2*a;i++) s1+="A";
                        for(int i=1;i<=m-2*b;i++) s2+="C";
                        for(int i=1;i<=b;i++) s2+="AC";
                        printf("%s\n%s\n",s1.c_str(),s2.c_str());
                        return 0;
                    }
                    // s2开头留C,结尾留A
                    if(b<m/2) {
                        // s1开头留C
                        if(a*A+b*B+BA+BB==x) {
                            string s1,s2;
                            for(int i=1;i<=n-2*a;i++) s1+="C";
                            for(int i=1;i<=a;i++) s1+="AC";
                            s2+="C";
                            for(int i=1;i<=b;i++) s2+="AC";
                            for(int i=1;i<=m-2*b-1;i++) s2+="A";
                            printf("%s\n%s\n",s1.c_str(),s2.c_str());
                            return 0;
                        }
                        // s1结尾留A
                        if(a*A+b*B+AB+BB==x) {
                            string s1,s2;
                            for(int i=1;i<=a;i++) s1+="AC";
                            for(int i=1;i<=n-2*a;i++) s1+="A";
                            s2+="C";
                            for(int i=1;i<=b;i++) s2+="AC";
                            for(int i=1;i<=m-2*b-1;i++) s2+="A";
                            printf("%s\n%s\n",s1.c_str(),s2.c_str());
                            return 0;
                        }
                    }
                }
            }
            // s1,s2开头留C,结尾留A
            if(b<m/2) {
                // s1开头结尾都不留
                if(a*A+b*B+BB==x) {
                    string s1,s2;
                    s1+="B";
                    for(int i=1;i<=a;i++) s1+="AC";
                    for(int i=1;i<=n-2*a-1;i++) s1+="B";
                    s2+="C";
                    for(int i=1;i<=b;i++) s2+="AC";
                    for(int i=1;i<=m-2*b-1;i++) s2+="A";
                    printf("%s\n%s\n",s1.c_str(),s2.c_str());
                    return 0;
                }
                if(a<n/2 && a*A+b*B+AB+BA+BB==x) {
                    string s1,s2;
                    s1+="C";
                    for(int i=1;i<=a;i++) s1+="AC";
                    for(int i=1;i<=n-2*a-1;i++) s1+="A";
                    s2+="C";
                    for(int i=1;i<=b;i++) s2+="AC";
                    for(int i=1;i<=m-2*b-1;i++) s2+="A";
                    printf("%s\n%s\n",s1.c_str(),s2.c_str());
                    return 0;
                }
            }
        }
    }
    puts("Happy new year!");
    return 0;
}