CodeForces 379 D New Year Letter

传送门

• 题意

已知字符串(s_n)=(s_{n-2})+(s_{n-1}),给你(s_1)和(s_2)的长度(n),(m),求能使(s_k)中恰好含有(x)个"(AC)"的(s_1),(s_2),如果无法实现输出"Happy new year!"

• 思路

在 (s_k)中能构成(AC)的方法有四种

1. (s_1)或(s_2)中包含(AC);
2. (s_1)末尾为(C),(s_2)开头为(A);
3. (s_2)末尾为(C),(s_1)开头为(A);
4. (s_2)末尾为(A),开头为(C);

然后用递推分别求出这四种情况到(s_k)时能够产生的(AC)数,再暴力分类讨论就好了。

• 代码

还是不贴出来了过于臭长

• 更好的解法

wpc神仙的博客里有讲,这里就不献丑了

传送门