2019 kickstart H

problemA

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <cstring>
#include <map>
#include <stack>
#include <functional>
#include <set>
#include <math.h>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <cstdio>
#include <sstream>
#define ll long long int
#define ld long double
#define fr(i, a, b) for(int i = a; i < b; i++)
#define frb(i, a, b) for(int i = a; i >= b; i--)
#define sq(x) ((x) * (x))
#define PI ( acos(-1.0) )
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define px first
#define py second
using namespace std;

int t;
int a, b;

int _char_to_int(char c) {
	if (c == 'R') {
		return 0;
	}
	else {
		return 1;
	}
}

class Trie {
public:
	bool finish;
	Trie *next[2];

	Trie() :finish(false) {
		memset(next, NULL, sizeof(next));
	}
	
	~Trie() {
		fr(i, 0, 2) {
			if (next[i]) {
				delete next[i];
			}
		}
	}

	void insert(string word) {
		Trie *tr = this;
		int idx = 0;
		int word_size = word.size();
		
		if (!word_size) {
			return;
		}

		for (; idx < word_size - 1; idx++) {
			int nw = _char_to_int(word[idx]);
			if (tr->next[nw] == NULL) {
				tr->next[nw] = new Trie();
			}
			tr = tr->next[nw];
		}
		if (tr->next[_char_to_int(word[idx])] == NULL) {
			tr->next[_char_to_int(word[idx])] = new Trie();
		}
		tr = tr->next[_char_to_int(word[idx])];
		tr->finish = true;
	}

	bool find(string word) {
		Trie *tr = this;
		int idx = 0;
		for (; idx < word.size() - 1; idx++) {
			if (tr == NULL) {
				return false;
			}
			int nw = _char_to_int(word[idx]);
			if (tr->next[nw] == NULL) {
				return false;
			}
			tr = tr->next[nw];
		}

		if (tr == NULL || tr->next[_char_to_int(word[idx]) == NULL]) {
			return false;
		}
		tr = tr->next[_char_to_int(word[idx])];
		return tr->finish;
	}

	ll sum(Trie *tr, int cnt) {
		ll ans = 0;

		if (tr->finish) {
			return (ll)1 << (a - cnt);
		}
		fr(i, 0, 2) {
			if (tr->next[i] != NULL) {
				ans += sum(tr->next[i], cnt + 1);
			}
		}
		return ans;
	}
};


void solve() {
	Trie *tr = new Trie();
	string str;
	cin >> a >> b;
	fr(i, 0, b) {
		cin >> str;
		tr->insert(str);
	}

	ll ans = (ll)1 << a;
	cout << ans - tr->sum(tr, 0) << "\n";

}

void init() {
	cin >> t;
	fr(i, 0, t) {
		cout << "Case #" << i+1 << ": ";
		solve();
	}
}



int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	init();
	//solve();
	system("pause");
	return 0;
}