miptalgo2015/Smth.cpp at master · mamaevads/miptalgo2015 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <algorithm>

using namespace std;
const int MAXLENS = 5;
const int MAXN = 100;
int d[MAXN / 2 + 1][1 << MAXLENS];

int convertFromBinary(const vector<int>& digits) {
	int p = 1, res = 0;
	for (int c : digits)
	{
		res += c * p;
		p *= 2;
	}
	return res;
}

int main() {
#ifdef HOME
#endif
	int n; string in;
	cin >> n >> in;
	if (in.length() == 1) {
		cout << (n >= 1);
		return 0;
	}
	int m = n / 2 + n % 2;
	int k = min((int)in.length() - 1, m);
	int numMasks = 1 << k;
	for (int msk = 0; msk < numMasks; msk++)
		d[k][msk] = 1;

	set<int> banned;
	vector<int> digits;
	for (char symb : in)
		digits.push_back(symb - 'A');
	banned.insert(convertFromBinary(digits));
	reverse(digits.begin(), digits.end());
	banned.insert(convertFromBinary(digits));

	for (int len = k + 1; len <= m; len++)
		for (int msk = 0; msk < numMasks; msk++)
			for (int prevDigit = 0; prevDigit < 2; prevDigit++) {
				int prevMsk = prevDigit + ((msk << 1) & (numMasks - 1));
				int allMsk = (msk << 1) + prevDigit;
				if (!banned.count(allMsk)) {
					d[len][msk] += d[len - 1][prevMsk];
					// cerr << d[len][msk] << endl;
				}
			}
	int ans = 0;
	for (int leftMsk = 0; leftMsk < numMasks; leftMsk++) {
		string left;
		int msk = leftMsk;
		for (int i = 0; i < k; i++)
		{
			left += char('A' + msk % 2);
			msk /= 2;
		}
		string right = left;
		if (n % 2 && k)
			right.pop_back();
		reverse(right.begin(), right.end());
		string medium = left + right;
		bool ok = (medium.find(in) == string::npos);
		reverse(medium.begin(), medium.end());
		ok &= (medium.find(in) == string::npos);
		if (ok) {
			ans += d[m][leftMsk];
		}
	}
	cout << ans << endl;
	//system("pause");
	return 0;
}