### 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;

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)