<h2>题目描述</h2>

令 $s_i$ 表示第 $i$ 个字符串，我们有递推式 $s_i = s_{i-2}+s_{i-1}$（其中+ 是将两个字符串拼接起来的符号）
现在需要你构造出长度为 $n$ 的 $s_1$ 和长度为 $m$ 的 $s_2$ ，满足 $s_k$ 中串 AC 作为子串出现了 $x$ 次。
$3 \leq k \leq 50,0 \leq x \leq 10^9,1 \leq n,m \leq 100$

<h2>题解</h2>

这个题还挺有意思的... dp 可以记录一些状态，不只是记录一个孤零零的值。
首先我们发现最后只需要关心的是 $AB$ 的数量，可能就会想到令 $f_{i}$ 表示 $s_i$ 的 AC 的数量，转移直接 $f_i = f_{i-1}+f_{i-2}$。但这显然不太对，因为中间可能还会拼接起来。
这时候我们的 dp 数组就要多记录点东西了：考虑类似于线段树维护最大字段和那样，$f_i$ 记录一个三元组 $(a,b,c)$ 表示左边的字母是 $a$，AC 的数量为 $b$ ，右边的字母为 $c$ 的数量。拼接的时候只需要看左边字符串的最右端和右边字符串的最左端 更新一下 $b$ 就好了。
然后我们发现 $n,m,k$ 都很小，一个自然的想法是枚举。但是一开始可能会发现枚举要确定头尾是什么字母，还要确定后面会不会和头尾产生新的 AC... 太麻烦了。但是仔细一想可以发现我们其实只需要确定 AC 的个数和头是不是 C，结尾是不是 A 就可以了。这些情况是不会对里面产生影响的，并且产生影响的情况和左右都填其他字母的情况等价。（要不是看了题解发现这种枚举方法我估计就要写大大大分类讨论了 qaq）
然后直接模拟输出就可以了.

<h2>代码</h2>

/*
 * sto Qingyu orz
 * 感谢真神sqy无私的教诲。膜时队者处处阿克，只因大师sqy在他背后。不膜大师者违背了真神的旨意，真神必将降下天谴,
 * 使其天天爆零
 * 我不由自主地膜拜真神sqy。
 * Author: RainAir
 * Time: 2019-10-21 15:25:35
 */
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define U unsigned
#define P std::pair
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
#define int LL
int k,x,n,m;
const int MAXN = 50+5;

struct Node{
    int l,cnt,r;
    // 1:A 2:B 3:others

    Node(int l=0,int cnt=0,int r=0) : l(l),cnt(cnt),r(r) {}

    friend Node operator + (const Node &a,const Node &b){
        Node res;res.cnt = a.cnt+b.cnt;
        res.l = a.l;res.r = b.r;
        if(a.r == 1 && b.l == 2) res.cnt++;
        return res;
    }
}f[MAXN];

inline void calc(){
    FOR(i,3,k) f[i] = f[i-2]+f[i-1];
}

signed main(){
    scanf("%lld%lld%lld%lld",&k,&x,&n,&m);
    FOR(i,0,n/2){
        FOR(j,0,m/2){
            FOR(a,0,1) FOR(b,0,1) FOR(c,0,1) FOR(d,0,1){
                if(i2+a+b > n || j2+c+d > m) continue;
                f[1] = Node(a?2:3,i,b?1:3);
                f[2] = Node(c?2:3,j,d?1:3);
                calc();
                if(f[k].cnt == x){
                    if(a) putchar('C');
                    FOR(k,1,i) putchar('A'),putchar('C');
                    FOR(k,i*2+a+1,n-b) putchar('X');
                    if(b) putchar('A');
                    puts("");
                    if(c) putchar('C');
                    FOR(k,1,j) putchar('A'),putchar('C');
                    FOR(k,j*2+c+1,m-d) putchar('X');
                    if(d) putchar('A');
                    puts("");
                    return 0;
                }
            }
        }
    }
    puts("Happy new year!");
    return 0;
}