Counting the number of increasing sub-sequences

Question

The problem is to find the number of increasing sub-sequence of a string with only digit characters. Answer may be very large, so output it modulo 10^9+7.

I have been able to get a O(n) solution using segment trees. However , the the code is quite inefficient owing to loops with constant but large runtime. How can I make the code more efficient ?

The link to the exact problem statement is http://www.spoj.com/problems/LARSUBP/

#include <stdio.h>
#include <string.h>


typedef struct Tree_node
{
    int M[10][10] ; 
    // M[i][j] = Number of sub-sequences starting with i and ending with j in the interval low to high in which it is called . 
} TN ;


//Declaration of global variables

char number[50000] ;//Stores the input string
TN Tree[100000] ;//The array Tree[] is used to store the nodes of the segment tree
long long int convert ; //Other variables
int k1 , k2, i , j; 



void Build_Tree( int node , int low , int high) ;

int main()
{
    // t is the number of test cases
    // N is the length of input string
    int t , N , counter ; 

    //Stores the number of increasing sub-sequences
    long long int answer ;

    //No of test cases
    scanf("%d",&t) ; 

    for(counter=0;counter<t;counter++)
    {
        scanf("%s",number) ; 
        N = strlen(number) ; 

        // Calling the build tree function 
       Build_Tree(1,0,N-1) ; 

        // Calculation of increasing sub-sequences using the Tree . 
        answer = 0 ;
       for(i=0;i<10;i++)
       {
           for(j=i;j<10;j++)
           {
              answer = answer + Tree[1].M[i][j] ; 
              answer= answer % 1000000007 ; 
           }
       }
       answer = answer %1000000007 ; 
       printf("%lld\n",answer) ; 

    }
    return 0 ; 
} 

void Build_Tree( int node , int low , int high)
{

 // node stores the index of the Tree-node to be evaluated
 // low and high define the interval which we are considering

    int mid ;   

    // Initialization of M[][]
    for(i=0;i<10;i++)
    {
        for(j=0;j<10;j++)
        {
            Tree[node].M[i][j] =0 ; 

        }
    }

    if(low==high)
    {
        // Base case 
        int temp = number[low]- '0' ; 
        Tree[node].M[temp][temp] = 1 ; 
    }
    else
    {
        mid = (low+high)/2 ; 
        Build_Tree(2*node , low , mid) ; // Building the subtree of left child
        Build_Tree(2*node+1 , mid+1 , high) ; // Building the subtree of right child


    // Combining the information 
    // No. of increasing sub-sequences starting with i and ending withj from low to highequal to sum of 
    // 1.increasing sub sequences starting with i and ending with j from low to mid
    // 2.increasing sub sequences starting with i and ending with j mid+1 to high
    //3. all increasing sub-sequences starting with i and ending with k1 from low to mid multiplied by increasing sub sequences starting with k2 and ending with j from mid+1 to high where k1 < k2 . 

        for(i=0;i<10;i++)
        {
            for(j=i;j<10;j++)
            {
                convert = Tree[2*node].M[i][j] + Tree[2*node+1].M[i][j] ; 
                convert = convert % 1000000007 ; 
                Tree[node].M[i][j] = convert ; 

                if(i==j)
                {
                    continue ;
                }
                else
                {

                    for(k1=i;k1<j;k1++)
                    {
                        for(k2=k1+1;k2<=j;k2++)
                        {
                            convert = Tree[node].M[i][j] + Tree[2*node].M[i][k1] * Tree[2*node+1].M[k2][j] ;
                            convert = convert % 1000000007 ;
                            Tree[node].M[i][j] = convert ; 

                        }
                    }
                }

            }
        }


    }



}

Answer 1

\$\newcommand{\sub}[1]{\text{sub}_{#1}}\$ This is more of an alternative algorithm than a review on your code (at least for now), but it seems like both could be helpful.

A good algorithm results from solving a slightly more informative version of the problem, which is simpler to decompose:

\$\sub{s}^n\$ is the number of subsequences of \$s\$ that are ordered and end with the digit \$n\$.

\$\sub{s}\$ can be stored in a 10-long array, the sum of which solves your original problem:

$$ \left[\ \sub{s}^0;\ \text{sub}_s^1;\ \text{sub}_s^2;\ \ldots;\ \text{sub}_s^9\ \right] $$

Clearly, for the empty string \$\varnothing\$, we have

$$ \text{sub}_\varnothing = \left[\ 0;\ 0;\ 0;\ \ldots;\ 0\ \right] $$

The interesting trick is that extending a string \$s\$ with digit \$d\$ is a simple update

$$ \sub{sd}^n = \begin{cases} \sub{s}^n & \text{if}\;n \ne d\\ 1 + \sum_{i=0}^{n} \sub{s}^i & \text{if}\;n = d \end{cases} $$

as the paths for subsequences that don't end in \$d\$ are unchanged and the subsequences that do end in \$d\$ are \$d\$ itself, \$d\$ added to the end of any prior subsequence that ends in a digit less than \$d\$, or any of the prior subsequences that did end with the digit already.