C. Codejamon Cipher

C. Codejamon Cipher

Explanation: Google Dynamic Programming Problem (APAC 2017 Round D) 

Code:

 

	#include <bits/stdc++.h>
	using namespace std;
	#define INF 1<<30
	#define endl '\n'
	#define maxn 500005
	#define tc printf("Case %d: ", cs)
	#define tcn printf("Case %d:\n", cs);
	#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	typedef long long ll;
	const double PI = acos(-1.0);
	#define dbg(x) cerr << #x << " = " << x << endl;
	#define dbg2(x, y) cerr << #x << " = " << x << ", " << #y << " = " << y << endl;
	#define dbg3(x, y, z) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
	#define dbg4(w,x, y, z) cerr << #w << " = " << w << ", " <<#x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
	const int Mod = 1e9 + 7;
	map<string, int> cnt;
	set<string>wordList;
	int lmt;
	int len;
	ll dp[maxn];
	string s;
	ll solve(int pos)
	{
	if (pos == len) return 1;
	string cur = "";
	ll &ans = dp[pos];
	if (ans != -1) return ans;
	ans = 0;
	int to = pos + lmt + 1;
	to = min(to, len);
	for (int i = pos; i < to; i++) {
	cur += s[i];
	sort(cur.begin(), cur.end());
	if (cnt[cur]) {
	ans += (cnt[cur] * solve(i + 1)) % Mod;
	if (ans >= Mod) ans -= Mod;
	}
	}
	return ans;
	}
	int main()
	{
	FASTIO
	///*
	//double start_time = clock();
	#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	freopen("error.txt", "w", stderr);
	#endif
	//*/
	int T;
	cin >> T;
	for (int cs = 1; cs <= T; cs++) {
	int n, q;
	cin >> n >> q;
	cnt.clear();
	wordList.clear();
	lmt = 0;
	for (int i = 0; i < n; i++) {
	string word;
	cin >> word;
	lmt = max(lmt, (int)word.length());
	wordList.insert(word);
	sort(word.begin(), word.end());
	cnt[word]++;
	}
	cout << "Case #" << cs << ": ";
	while (q--) {
	cin >> s;
	len = s.length();
	for (int i = 0; i <= len; i++) dp[i] = -1;
	cout << solve(0) << " ";
	}
	cout << endl;
	}
	//double end_time = clock();
	//printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
	return 0;
	}

view raw Google Dynamic Programming Problem (APAC 2017 Round D).cpp hosted with ❤ by GitHub

Share: