Spoj FANCY

LOGIC:

For this problem we will try a mathematical approach first analyze given examples that how we can apply mathematical formulas for given input.

N = 12345
there is only one way to represent this string which is One 1, One 2, One 3, One 4, One 5

N = 11112
there are 8 way to represent this string which are :
        One 1, One 1, One 1, One 1, One 2
        One 1, One 1, Two 1, One 2
        One 1, Three 1, One 2
        Four 1, One 2
        One 1, Two 1, One 1, One 2
        Three 1, One 1, One 2
        Two 1, One 1, One 1, One 2
        Two 1, Two 1, One 2
in above example we can see that 2 occurred 1 time so  there is only 1 arrangement for 2,
now analyze for 1 , 1 occurred 4 time so we can represent it in 8 ways , now question is why?
as we know we can decompose 4 in 8 ways like:
       1 + 1 + 1 + 1
       1 + 1 + 2
       1 + 2 + 1
       1 + 3
       4
       2 + 1 + 1
       2 + 2
       3 + 1
       so here problem is in how many ways we can split K where K is some number here K = 4
Well this standard problem and you can find solution using two methods 1. Pattern recognition 2. Combinatorics

1. Pattern recognition :-
               N = 1      Ways  -> 1
               N = 2      Ways  -> 2
               N = 3      Ways  -> 4
               N = 4      Ways  -> 8
            we can find Ways using pen paper and by looking pattern we can say that it can be 
            2 ^ (N - 1)     ::where  ^ is power sign
            but this is trial and error method and no proof of its correctness 

2. Combinatorics:-  
              N = 1    Ways   ->   0 C 0 = 1
              N = 2    Ways   ->   1 C 0 + 1 C 1 = 2
              N = 3    Ways   ->   2 C 0 + 2 C 1 + 2 C 2 = 4
              N = 4    Ways   ->   3 C 0 + 3 C 1 + 3 C 2 + 3 C 3 = 8
              :: Where nCr mean ways to choose r items from n items  n! / (r! n-r!)   where '!' 
             mean factorial
             so for some N it will be (N - 1) C 0 + (N - 1) C 1 + ..... + (N - 1) C (N - 1) and we know                    that it is equal to 2 ^ (N - 1) (Need proof then google it ;) ) 
             Well why we choose N - 1 is homework for readers :D


Now we can find ways for single element which occurring continuously K time which is 2 ^ (K - 1)
but in our problem we have many elements which are occurring.
so suppose N = a1 a2 ....aK1 b1 b2 b3 ... bK2 c1 c2 c3 ... cK3
then first of all we will find 2 ^(K1 - 1) , 2 ^ (K2 - 1), 2 ^ (K3 - 1) independently all ways in which we can arrange and then we will multiply them because order will not change
so answer will be 2 ^ (K1 - 1) * 2 ^(K2 - 1) * 2^(K3 - 1).

Below you can see code also   

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
using namespace std; 
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)
inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
const int INF = 1<<29;
typedef long long ll;
inline int two(int n) { return 1 << n; }
inline int test(int n, int b) { return (n>>b)&1; }
inline void set_bit(int & n, int b) { n |= two(b); }
inline void unset_bit(int & n, int b) { n &= ~two(b); }
inline int last_bit(int n) { return n & (-n); }
inline int ones(int n) { int res = 0; while(n && ++res) n-=n&(-n); return res; }
template<class T> void chmax(T & a, const T & b) { a = max(a, b); }
template<class T> void chmin(T & a, const T & b) { a = min(a, b); }
/////////////////////////////////////////////////////////////////////


int main()
{
int T;
scanf("%d", &T);

while(T--) {
char Str[50];
scanf("%s", Str);
int len = strlen(Str);
int cnt = 0;
int ans = 1;
for(int i = 0; i < len; ++i) {
if(i == 0) {
cnt = 1;
} else {
if(Str[i] == Str[i - 1]) {
cnt++;
} else {
ans *= (1 << (cnt - 1));
cnt = 1;
}
}
}
if(cnt > 0)
ans *= (1 << (cnt - 1));
printf("%d\n", ans);
}
    return 0;
}


Happy Coding :)