Submission #54014177

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#define mems(x, v) memset(x, v, sizeof x)
#define mcpy(x, y) memcpy(x, y, sizeof x)
using namespace std;
typedef pair <int, int> pii;
typedef long long ll;
typedef unsigned long long ull;
typedef long double wisdom;

struct Node {int nxt, val;} trans[15][2];
map <string, int> id; int dis[15];
void insert(string s, char ch, int val, string to) {trans[id[s]][ch == 'A' ? 0 : 1] = (Node){id[to], val};}
void tick(string s, int val) {dis[id[s]] = val;}

void prepare() {
	id["A"] = 0, id["B"] = 1,
	id["AA"] = 2, id["BB"] = 3,
	id["AAA"] = 4, id["BBB"] = 5,
	id["AAAA"] = 6, id["BBBB"] = 7, //AAAA: 当前在B且下一段A选择跳过
	id["AB"] = 8, id["BA"] = 9,
	id["O"] = 10, id["OA"] = 11, id["OB"] = 12;

	insert("A", 'A', 0, "AA"), insert("A", 'B', 0, "AB");
	insert("B", 'A', 0, "BA"), insert("B", 'B', 0, "BB");
	insert("AA", 'A', 0, "AAA"), insert("AA", 'B', 1, "AB");
	insert("BB", 'A', 1, "BA"), insert("BB", 'B', 0, "BBB");
	insert("AAA", 'A', 1, "AAAA"), insert("AAA", 'B', 2, "O");
	insert("BBB", 'A', 2, "O"), insert("BBB", 'B', 1, "BBBB");
	insert("AAAA", 'A', 0, "AAAA"), insert("AAAA", 'B', 1, "B");
	insert("BBBB", 'A', 1, "A"), insert("BBBB", 'B', 0, "BBBB");
	insert("AB", 'A', 1, "O"), insert("AB", 'B', 0, "BBBB");
	insert("BA", 'A', 0, "AAAA"), insert("BA", 'B', 1, "O");
	insert("O", 'A', 0, "OA"), insert("O", 'B', 0, "OB");
	insert("OA", 'A', 0, "AAAA"), insert("OA", 'B', 1, "O");
	insert("OB", 'A', 1, "O"), insert("OB", 'B', 0, "BBBB");

	tick("A", 1), tick("B", 1);
	tick("AA", 2), tick("BB", 2);
	tick("AAA", 2), tick("BBB", 2);
	tick("AAAA", 1), tick("BBBB", 1);
	tick("AB", 1), tick("BA", 1);
	tick("O", 1), tick("OA", 1), tick("OB", 1);
}

const int mod = 1e9 + 7;
int dp[4005][2005][15]; //dp[i][j][s]: 前i个点走了j步且当前状态为s，方案数

int main() {
	int n, k, ans = 0; string A;
	cin >> n >> k >> A, prepare();
	dp[0][0][id["O"]] = 1;
	for (int i = 0; i < n; i++)
		for (int j = 0; j <= k; j++) for (int s = 0; s <= 12; s++) {
			if (A[i] == '?' || A[i] == 'A') (dp[i + 1][j + trans[s][0].val][trans[s][0].nxt] += dp[i][j][s]) %= mod;
			if (A[i] == '?' || A[i] == 'B') (dp[i + 1][j + trans[s][1].val][trans[s][1].nxt] += dp[i][j][s]) %= mod;
		}
	for (int i = 0; i <= k; i++) for (int s = 0; s <= 12; s++)
		if (i + dis[s] <= k) ans = (ans + dp[n - 1][i][s]) % mod;
	cout << ans;
	return 0;
}

Submission Info

Judge Result