LARSUBP-Large subsequence Problem

Large subsequence Problem

Given below code is for larsubp spoj or Large subsequence Problem spoj. 

Here the problem is simple we have to use DP .

Let given string be S then the number subsequence for any integer s[i] will be sum of all indices less then 'i' which are having integer less then s[i] + 1 (for s[i] )

let take an example s = 7598 

for 7 ans will be one because no character before it.

for 5 ans will be one because character before it is not less then 5;

for 9 ans is '3' because before it there are two character less then '9' so solution will be (ans for 7 + ans for 5 + 1)

similarly for 8 ans will be '3' two character before it are less then '8';

We can implement the above logic using hash table ;

See the python code for understanding .

If you found difficulty you can mail me @ raj.nishant360@gmail.com
Below given c++ code;

#include <bits/stdc++.h> 
using namespace std;
#define MOD 1000000007
int main() { 
    int t;
    scanf("%d ",&t); 
    for(int p=1;p<=t;p++) 
    { 
        char s[10009]; 
        scanf("%s",s);
        int prev[11];
        for(int i=0;i<10;i++) 
            prev[i] =0; 
        int sum = 0; 
        int j=-1,k,temp;
        while(s[++j]!='\0') 
        {
            k = s[j] - 48; 
            temp = k; 
            while(k--)
                prev[temp] = (prev[temp]+ prev[k])%MOD;
            prev[temp]++;
        }
        for(int i=0;i<=9;i++)
            sum = (sum + prev[i])%MOD;
        printf("Case %d: %d\n",p,sum);
    } 
    return 0; 
}

Below given python code;

import sys
t=int(sys.stdin.readline())
for p in xrange(1,t+1):
    s=raw_input()
    pre=[]
    for i in xrange(0,10):
        pre.append(0)
    su=0
    for i in xrange(0,len(s)):
        k = int(s[i])
        temp = k;
        k-=1
        while k>=0:
            pre[temp] = pre[temp] + pre[k]
            k-=1
        pre[temp]+=1
    for i in xrange(0,10):
        su = su+pre[i]
    res =""
    su = su%1000000007
    res=res + "Case "+str(p)+": "+str(su)
    print(res)