duel 的时候差点不会 2400 了。
套路地，考虑每个 \(F(x)\) 中与 \(s\) 相同的子序列的贡献。设这个子序列为 \(F(x)_{p_1}, F(x)_{p_2}, F(x)_{p_3}, \ldots, F(x)_{p_n}\)。
我们想要它成为一个子序列的子串，那么 \(F(x)_{[p_1, p_n]}\) 中除了 \(p_1 \sim p_n\) 就不能有别的字符被选。而 \([1, p_1 - 1] \cup [p_n + 1, |F(x)|]\) 中的每个字符都可以选或不选，相当于每个字符产生 \(2\) 的贡献。
如果我们设 \(f_{i, j}\) 为考虑到 \(F(x)\) 的第 \(i\) 位，匹配到 \(s\) 的第 \(j\) 位的答案，那么相当于 \(f_{i + 1, 0} \gets 2 f_{i, 0}, f_{i + 1, n} \gets 2 f_{i, n}, \forall j \in [1, n - 1], f_{i + 1, j} \gets f_{i, j}, \forall j \in [1, n] \land F(x)_i = s_j, f_{i + 1, j} \gets f_{i, j - 1}\)。答案即为 \(f_{|F(x)|, n}\)。
可以用矩阵刻画这个转移过程。设 \(F_i\) 为 \(F(i)\) 的转移矩阵，那么 \(F_i = F_{i - 1} F_{i - 2}\)。
时间复杂度 \(O(n^3x)\)。
code
// Problem: F. Fibonacci String Subsequences
// Contest: Codeforces - Educational Codeforces Round 39 (Rated for Div. 2)
// URL: https://codeforces.com/problemset/problem/946/F
// Memory Limit: 256 MB
// Time Limit: 3500 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 110;
const ll mod = 1000000007;
ll n, m;
char s[maxn];
struct mat {
ll a[110][110];
mat() {
mems(a, 0);
}
} f[maxn];
inline mat operator * (const mat &a, const mat &b) {
mat res;
for (int k = 0; k <= n; ++k) {
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= n; ++j) {
res.a[i][j] = (res.a[i][j] + a.a[i][k] * b.a[k][j]) % mod;
}
}
}
return res;
}
void solve() {
scanf("%lld%lld%s", &n, &m, s + 1);
f[0].a[0][0] = f[0].a[n][n] = f[1].a[0][0] = f[1].a[n][n] = 2;
for (int i = 1; i < n; ++i) {
f[0].a[i][i] = f[1].a[i][i] = 1;
}
for (int i = 1; i <= n; ++i) {
if (s[i] == '0') {
f[0].a[i - 1][i] = 1;
} else {
f[1].a[i - 1][i] = 1;
}
}
for (int i = 2; i <= m; ++i) {
f[i] = f[i - 1] * f[i - 2];
}
mat ans;
ans.a[0][0] = 1;
ans = ans * f[m];
printf("%lld\n", ans.a[0][n]);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}