枚举s1,s2字串的纯AC的个数。
然后加上s1-s2,s2-s1,s1-s1,s2-s2中产生的AC的个数。
注意：数的范围
#include <stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<stdlib.h>
#include<math.h>
#include<stack>
#define LL __int64
#define maxn 20000
using namespace std;
LL num[55][7];//1,2,12,21,11,22
int wei[55];
int shou[55];
int k,s,n,m;
int t1,t2,t3;
void init()
{int i,j;memset(num,0,sizeof(num));num[1][1]=1;num[2][2]=1;wei[1]=shou[1]=1;wei[2]=shou[2]=2;for(i=3;i<=50;i++){for(j=1;j<=6;j++)num[i][j]=num[i-2][j]+num[i-1][j];if(wei[i-2]==1){if(shou[i-1]==1)num[i][5]++;else num[i][3]++;}else{if(shou[i-1]==1)num[i][4]++;else num[i][6]++;}wei[i]=wei[i-1];shou[i]=shou[i-2];}
}
int dos(int need,int xx,int yy)
{/// cout<<need<<endl;int i,j;int a[4]={1,1,2,0};int b[4]={1,1,0,2};int a1,a2;int b1,b2;a1=a2=b1=b2=0;for(i=0;i<(1<<4);i++){int x,y;x=xx;y=yy;a1=a2=b1=b2=0;int leaps=1;int nn;nn=0;for(j=0;j<4;j++){if(i&(1<<j)){if(j==0)a2=b1=1;if(j==1)a1=b2=1;if(j==2)a1=a2=1;if(j==3)b1=b2=1;}}if(a1+a2>xx)continue;if(b1+b2>yy)continue;if(a2==1&&b1==1)nn+=num[k][3];if(a1==1&&b2==1)nn+=num[k][4];if(a2==1&&a1==1)nn+=num[k][5];if(b2==1&&b1==1)nn+=num[k][6];if(nn==need){t3=i;return 1;}}return 0;
}
void print()
{// cout<<t1<<" "<<t2<<" "<<t3<<endl;int i,j;char stra[501];char strb[501];for(i=0;i<201;i++)stra[i]=strb[i]='B';for(i=0;i<4;i++){if((1<<i)&t3){if(i==0)stra[n-1]='A',strb[0]='C';if(i==1)stra[0]='C',strb[m-1]='A';if(i==2)stra[0]='C',stra[n-1]='A';if(i==3)strb[0]='C',strb[m-1]='A';}}if(stra[0]=='B')i=0;else i=1;for(j=1;j<=t1;j++){stra[i]='A';stra[i+1]='C';i+=2;}if(strb[0]=='B')i=0;else i=1;for(j=1;j<=t2;j++){strb[i]='A';strb[i+1]='C';i+=2;}for(i=0;i<n;i++)cout<<stra[i];cout<<endl;for(i=0;i<m;i++)cout<<strb[i];cout<<endl;
}
int main()
{int i,j;init();// for(i=1;i<=6;i++)cout<<num[i][6]<<endl;//cout<<num[48][2]<<endl;// cout<<num[48][3]<<endl;while(~scanf("%d%d%d%d",&k,&s,&n,&m)){int leap=0;for(i=0;i*2<=n;i++){for(j=0;j*2<=m;j++){t1=i;t2=j;t3=0;LL xx=num[k][1]*i;LL yy=num[k][2]*j;//cout<<xx<<" "<<yy<<endl;if(xx+yy>s){leap=0;break;}if(xx+yy==s){leap=1;break;}if(dos(s-xx-yy,n-i*2,m-j*2)){leap=1;break;}}if(leap==1)break;}if(leap==1)print();else cout<<"Happy new year!"<<endl;}return 0;
}