LARSUBP - Large subsequence Problem - SPOJ Solution C++ ~ CodingWithArt

➤ Problem Link : LARSUBP

👉 Hint : edit please

✅ C++ Solution :

 
#include<bits/stdc++.h>

using namespace std;
#define ll long long int
ll m=pow(10,9)+7;
ll dp[10002][10];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll p,t;
	cin>>t;
    for(ll p=1;p<=t;p++)
	{
		ll ans=0;
		string s;
		cin>>s;
		memset(dp,0,sizeof(dp));
		for(ll i=0;i<s.length();i++)
			dp[i][s[i]-'0']=1;
		for(ll i=1;i<s.length();i++)
		{
			for(ll j=0;j<10;j++)
				dp[i][j]=(dp[i][j]+dp[i-1][j])%m;
			for(ll j=0;j<s[i]-'0';j++)
				dp[i][s[i]-'0']=(dp[i][s[i]-'0']+dp[i-1][j])%m;
		}
		for(ll j=0;j<10;j++)
			ans=(ans+dp[s.length()-1][j])%m;
		cout<<"Case "<<p<<": "<<ans<<endl;	
	}
}

Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.

😇Happy Learning!!

About Utkarsh Gupta

I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.