题意:长度为\(n\)的只含有"C"或"P"的字符串共有\(2^n\)个,问:这所有\(2^n\)个字符串中含有多少个"CCPC"(每一个"CCPC"之间不能相互重叠,即"CCPCCPC"中只能算\(1\)个"CCPC")
分析:
假设所有长度为\(n\)的"CP"字符串中互不重叠的"CCPC"的个数为\(a_n\)
若认为可以相互重叠,可以通过计算贡献的方式进行计算
// 1. CCPC***...*****(只关注子串[1...4]的贡献) // 2. *CCPC**...*****(只关注子串[2...5]的贡献) // 3. **CCPC*...*****(只关注子串[3...6]的贡献) // 4. ***CCPC...*****(只关注子串[4...7]的贡献) // 5. ****CCP...*****(只关注子串[5...8]的贡献) // 6. *****CC...*****(只关注子串[6...9]的贡献) // . // . // . //n-4. *******...CCPC*(只关注子串[n-4...n-1]的贡献) //n-3. *******...*CCPC(只关注子串[n-3...n]的贡献)
"CCPC"有\((n-3)\)种摆法,剩下\((n-4)\)个字符随便选
答案即为\((n-3)\cdot2^{n-4}\)
然而,题目要求每一个"CCPC"之间不能相互重叠
可以发现
\(1,4\)发生重叠,\(2,5\)发生重叠,\(3,6\)发生重叠,...
和上面的计算方法一样
即"CCPCCPC"有\((n-6)\)种摆法,剩下\((n-7)\)个字符随便选
总共为\((n-6)\cdot 2^{n-7}\)
减掉这些,发现减多了
减多了哪些?
\(1,4,7\)发生重叠,\(2,5,8\)发生重叠,\(3,6,9\)发生重叠,...
即"CCPCCPCCPC"有\((n-9)\)种摆法,剩下\((n-10)\)个字符随便选
总共为\((n-9)\cdot 2^{n-10}\)
加上这些,发现加多了
加多了哪些?
……
以此类推,容斥原理
答案为\(a_{n}=\sum\limits_{i=1}^{\lfloor \frac{n}{3}\rfloor}(-1)^{i-1}\cdot(n-3i)\cdot 2^{n-3i-1}\)
从而有这个
\[\begin{aligned} a_{n-3}&=\sum\limits_{i=1}^{\lfloor \frac{n-3}{3}\rfloor}(-1)^{i-1}\cdot(n-3-3i)\cdot 2^{n-3-3i-1}\\ &=\sum\limits_{i=1}^{\lfloor \frac{n-3}{3}\rfloor}(-1)^{i-1}\cdot(n-3-3i)\cdot 2^{n-3-3i-1}\\ &=\sum\limits_{i=1}^{\lfloor \frac{n}{3}\rfloor-1}(-1)^{i-1}\cdot(n-3(i+1))\cdot 2^{n-3(i+1)-1}\\ &=\sum\limits_{i=2}^{\lfloor \frac{n}{3}\rfloor}(-1)^{i}\cdot(n-3i)\cdot 2^{n-3i-1}\\ \end{aligned} \]所以zyf大佬送给我的递推式\(a_n=(n-3)\cdot2^{n-4}-a_{n-3}\)是对的(干得漂亮)
然而这题到这还没完,题目条件\(1\leq n \leq 10^9\),线性递推搞不定
啊这,梦回高中
由于
\[\begin{aligned} a_n+a_{n-3}&=(n-3)\cdot2^{n-4}\\ \end{aligned} \]有
\[\begin{aligned} \frac{8a_n}{2^{n-1}}+\frac{a_{n-3}}{2^{n-4}}&=n-3\\ \end{aligned} \]令\(\frac{a_n}{2^{n-1}}=b_n\),有
\[8b_n+b_{n-3}=n-3\\ 8(b_n-\frac{1}{9}n)+b_{n-3}-\frac{1}{9}n+3=0\\ 8(b_n-\frac{1}{9}n)+b_{n-3}-\frac{1}{9}(n-3)-\frac{1}{3}+3=0\\ 8(b_n-\frac{1}{9}n+\frac{8}{27})+b_{n-3}-\frac{1}{9}(n-3)+\frac{8}{27}=0\\ \]令\(b_n-\frac{1}{9}n+\frac{8}{27}=c_n\),有
\[c_n=-\frac{1}{8}c_{n-3} \]由\(a_1=a_2=a_3=0\)及\(c_n=\frac{a_n}{2^{n-1}}-\frac{1}{9}n+\frac{8}{27}\)
\[c_1=\frac{5}{27}\\ c_2=\frac{2}{27}\\ c_3=-\frac{1}{27} \]所以
\[c_{3n}=-\frac{1}{27}\cdot(-\frac{1}{8})^{n-1}\\ c_{3n+1}=\frac{5}{27}\cdot(-\frac{1}{8})^{n}\\ c_{3n+2}=\frac{2}{27}\cdot(-\frac{1}{8})^{n}\\ \]由\(a_n=2^{n-1}(c_n+\frac{1}{9}n-\frac{8}{27})\)
\[a_{3n}=\frac{1}{54}(8\cdot(-1)^{n}+(9n-8)\cdot8^{n})\\ a_{3n+1}=\frac{1}{27}(5\cdot(-1)^{n}+(9n-5)\cdot8^{n})\\ a_{3n+2}=\frac{2}{27}(2\cdot(-1)^{n}+(9n-2)\cdot8^{n}) \]代码:
#include <cstdio> typedef long long Lint; const Lint mod = 1e9 + 7; Lint fpow(Lint a, Lint n) { Lint res = 1; for (; n; n >>= 1) { if (n & 1) res = res * a % mod; a = a * a % mod; } return res; } Lint minv(Lint a) { return fpow(a, mod - 2); } Lint ainv(Lint a) { return mod - a; } Lint mod_add(Lint a, Lint b) { return (a + b) % mod; } Lint mod_mul(Lint a, Lint b) { return a * b % mod; } Lint kn1n(Lint k, Lint n) { return n % 2 ? ainv(k) : k; } const Lint inv1 = minv(54); const Lint inv2 = minv(27); const Lint inv3 = mod_mul(2, inv2); int main() { int T; scanf("%d", &T); while (T--) { int n; scanf("%d", &n); int r = n % 3, k = n / 3; Lint res = 0; if (r == 0) { res = mod_mul(inv1, mod_add(kn1n(8, k), mod_mul(mod_add(mod_mul(9, k), ainv(8)), fpow(8, k)))); } else if (r == 1) { res = mod_mul(inv2, mod_add(kn1n(5, k), mod_mul(mod_add(mod_mul(9, k), ainv(5)), fpow(8, k)))); } else { res = mod_mul(inv3, mod_add(kn1n(2, k), mod_mul(mod_add(mod_mul(9, k), ainv(2)), fpow(8, k)))); } printf("%lld\n", res); } return 0; }