526互联

CodeForces 946F Fibonacci String Subsequences

发布时间 2023-10-24 16:15:54作者: zltzlt

洛谷传送门

CF 传送门

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;
}