for studious students II i came up with following solution during the contest but it didnt work in 6 min time.
is there a better solution possible. and how to do that.
Also can anyone provide a detailed explanation for problem A and C.


#include<map>
#include<iostream>
#include<string>
#include<queue>
using namespace std;
#define mod 1000000007
struct CompareMethod
{
bool operator()(const std::string &a, const std::string &b) const
{
if(a.length()>b.length())
    return 0;
return 1;
   
}
};

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        string s;
        cin >> s;
        map<string,int>dp;
        priority_queue<string,vector<string>,CompareMethod>q;
        dp[s]=1;
        q.push(s);
        while(!q.empty())
        {
            string n=q.top();
            //cout << n <<"\n";
            q.pop();
            for(int i=0;i<n.length();i++)
            {
                for(int j=i+1;j<n.length();j++)
                {    bool pa=0,pb=0;
                    for(int k=i;k<=j;k++)
                        if(n[k]=='a')
                            pa=1;
                        else
                            pb=1;
                    if(pa==1 && pb==1)
                    {    string tmp1,tmp2,tmp;
                        tmp1=n.substr(0,i);
                        tmp2=n.substr(j+1,n.length()-j);
                        tmp=tmp1+"a"+tmp2;
                        if(dp.find(tmp)==dp.end())
                            q.push(tmp);
                        dp[tmp]+=dp[n];
                        dp[tmp]=dp[tmp]%mod;
                        tmp1=n.substr(0,i);
                        tmp2=n.substr(j+1,n.length()-j);
                        tmp=tmp1+"b"+tmp2;
                   
                        if(dp.find(tmp)==dp.end())
                            q.push(tmp);
                        dp[tmp]+=dp[n];
                        dp[tmp]=dp[tmp]%mod;
                    }
                    else if(pa==1)
                    {    string tmp1,tmp2,tmp;
                        tmp1=n.substr(0,i);
                        tmp2=n.substr(j+1,n.length()-j);
                        tmp=tmp1+"a"+tmp2;
                        if(dp.find(tmp)==dp.end())
                            q.push(tmp);
                        dp[tmp]+=dp[n];
                        dp[tmp]=dp[tmp]%mod;
                    }
                    else if(pb==1)
                    {    string tmp1,tmp2,tmp;
                        tmp1=n.substr(0,i);
                        tmp2=n.substr(j+1,n.length()-j);
                        tmp=tmp1+"b"+tmp2;
                   
                        if(dp.find(tmp)==dp.end())
                            q.push(tmp);
                        dp[tmp]+=dp[n];
                        dp[tmp]=dp[tmp]%mod;
                    }
                }
            }
        }
        int ans=0;       
        for(map<string,int>::iterator it=dp.begin();it!=dp.end();it++)
        {    ans+=dp[it->first];//cout <<it->first << " : "<<dp[it->first] << "\n";
        }
        cout << ans << "\n";
    }
}

A recurrence is defined as
    F(x)=summation { F(y) : y is divisor of x and y!=x }
    F(1)=1
e.g. F(12)=F(1)+F(2)+F(3)+F(4)+F(6)=F(1)+F(2)+F(3)+F(1)+F(2)+F(1)+F(2)+F(3)=8

1 <  x  < 2^31
how can i solve this recurrence relation??

how to find permanent of a matrix in O(n * 2^n) ?? also can anyone explain ryser's formula or how to prove it ?? i could not understand why it works ??

in how many ways is it possible to place z identical rooks on a chessboard of dimension x*y such that every cell in the chessboard is threatened by at least one rook ??
plzz explain how to solve this problem??

is it possible to make segment tree to answer dynamic queries ????

how to extract a range from stl set..like if i have to extract all the elements from x-h to x+h from a set ...hw can i do it in log n   time?? i am trying to use lower_bound and upper_bound and iterating between the iterators found by them but its giving a lot of error to me..
plzz help..

i m doing this problem on spoj..i cant find any approach fr this..bt i feel this is to be done by sweep lines...hw to do this prob using sweep lines or by any other method??

i  m doing this (spoj SUBSEQ) problem on spoj...my algo is n*logn bt its giving me TLE ...hw this problem is to b solved ..i m using map...
here is the code...

int main()
{
     map<int,int>list;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        list.clear();
        int n;
        scanf("%d",&n);
        int tmp;
        VI a,sum(n+1);
        a.pb(0);
        FOR(i,1,n)
        {
            scanf("%d",&tmp);
            a.pb(tmp);
            sum[i]=tmp+sum[i-1];
            list[sum[i]]++;
        }
        list[0]++;
        int64 ans=0;
        int val;
        for(int i=n;i>=0;i--)
        {
            list[sum[i]]--;
            val=list[sum[i]-47];
            if(val>0)
                ans+=val;
        }
        printf("%lld\n",ans);
    }
}

i was solving this(http://www.spoj.pl/problems/LEGO/) problem in spoj..i tried it using disjoint set DS bt i m getting TLE..
wat i did was for each pair(total of n(n-1)/2 pairs) i checked whether they r connected or not ..if they are connected and their sets r different then i did a union operation for those pairs..
( total no. of sets in starting - total union operations ) gives me the num. of disconnected components..

is there any other method so tht i can avoid TLE(other thn building a graph and doing DFS to find out the no. of disconnected components)..

here is my code tht was TLEed..any optimization tht i can do in it???

thnx in advance fr ur reply..

i was solving the cutting sticks problem frm UVA(10003) ...the approach i used was tht suppose there r 'n' cuts...so i used all the 2^n subsets of this as states...bt this approach is wasting too much time and memory..i read somewhere tht this problem is exactly similar to matrix chain multiplication..bt i can not figure out the similarity(i could nt convince myself tht i will get the solution doing tht way)...so can anyone explain hw to solve this problem...
here is the link to the problem...
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=944