codechef/Count Subsequences .cpp at master · AnkurRyder/codechef · 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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define re(i, n) for(int i = 0; i < n; i++)
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define ren(i,a,b) for(int i = (a); i >= (b); i--)
#define si(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
#define ss(s) scanf("%s",s)
#define pi(x) printf("%d\n",x)
#define pl(x) printf("%lld\n",x)
#define ps(s) printf("%s\n",s)

string s;

ll count_sub(vector<vector<ll> >& dp , int a , int b)
{
	vector<bool> v(26);
	if(b < a)
		return 1;
	if(dp[a][b] != 0)
		return dp[a][b];
	rep(i , a , b)
	{
		if(!v[s[i]-65]){
			v[s[i]-65] = 1;
			dp[a][b] += count_sub(dp , i+1 , b);
		}
	}
	dp[a][b]++;
	return dp[a][b];
}

int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int t;
	si(t);
	while(t--)
	{
		cin >> s;
		vector<vector<ll> > dp(10005 , vector<ll>(10005));
		cout << count_sub(dp , 0 , s.length()-1) << "\n";
	}
	return 0;
}