令 \(c_i\) 为第 \(i\) 位带来的进位的值，令 \(c_{-1} = 0\)。
考虑如果知道了 \(c_{i - 1}, c_i\) 的值，\(a_i, b_i\) 有多少种选法：
- \(c_{i - 1} = 0, c_i = 0\)，\((a_i, b_i) = (0, 0), (0, 1), (1, 0)\)。
- \(c_{i - 1} = 1, c_i = 1\)，\((a_i, b_i) = (1, 1), (0, 1), (1, 0)\)。
- \(c_{i - 1} = 0, c_i = 1\)，\((a_i, b_i) = (1, 1)\)。
- \(c_{i - 1} = 1, c_i = 0\)，\((a_i, b_i) = (0, 0)\)。
于是可以观察到若 \(c_i = c_{i - 1}\)，\((a_i, b_i)\) 有 \(3\) 种选法，否则 \((a_i, b_i)\) 有 \(1\) 种选法。
于是若知道了 \(c_i\not c_{i - 1}\) 的个数 \(p\)，那么 \((a_i, b_i)\) 的选法就是 \(3^{n - p}\)。
那么就不需要考虑 \((a_i, b_i)\)，只用考虑 \(c_i\) 了。
那么如果算上 \(c_{-1}\)，因为 \(p\) 的定义所以可以知道 \(c_i = 0\) 有 \(\lceil\frac{p + 1}{2}\rceil\) 个连续段，\(c_i = 1\) 有 \(\lfloor \frac{p + 1}{2}\rfloor\) 个连续段。
同时因为限制了 \(c_i = 1\) 的个数为 \(k\)，相对也限制了 \(c_i = 0\) 的个数为 \(n + 1 - k\)。
所以 \(c_i\) 的方案数就是插板法得到 \(\binom{k - 1}{\lfloor \frac{p + 1}{2}\rfloor - 1}\times \binom{n - k}{\lceil\frac{p + 1}{2}\rceil - 1}\)。
所以固定 \(p\) 对应的方案数就是 \(3^{n - p}\times \binom{k - 1}{\lfloor \frac{p + 1}{2}\rfloor - 1}\times \binom{n - k}{\lceil\frac{p + 1}{2}\rceil - 1}\)。
那么枚举一下 \(p\) 即可，即求 \(\sum\limits_{p = 1}^n 3^{n - p}\times \binom{k - 1}{\lfloor \frac{p + 1}{2}\rfloor - 1}\times \binom{n - k}{\lceil\frac{p + 1}{2}\rceil - 1}\)。
注意判一下 \(k = 0\) 时所有 \(c_i\) 都为 \(0\) 答案为 \(3^n\) 的情况。
时间复杂度 \(\mathcal{O}(n)\)。
#include<bits/stdc++.h>
using ll = long long;
constexpr ll mod = 1e9 + 7;
inline ll qpow(ll a, ll b = mod - 2, ll v = 1) {
while (b) {
b & 1 && ((v *= a) %= mod);
b >>= 1, (a *= a) %= mod;
}
return v;
}
const int maxn = 1e6 + 10;
ll fac[maxn], invf[maxn];
inline ll binom(int n, int m) {
if (n < m) return 0;
return fac[n] * invf[n - m] % mod * invf[m] % mod;
}
int main() {
int n, k;
scanf("%d%d", &n, &k);
fac[0] = 1;
for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % mod;
invf[n] = qpow(fac[n]);
for (int i = n; i; i--) invf[i - 1] = invf[i] * i % mod;
if (! k) return printf("%lld\n", qpow(3, n)), 0;
ll ans = 0, v = 1;
for (int i = n; i; i--, (v *= 3) %= mod)
(ans += v * binom(k - 1, (i + 1) / 2 - 1) % mod * binom(n - k, (i + 2) / 2 - 1)) %= mod;
printf("%lld\n", ans);
return 0;
}