Submission #4037336

Source Code Expand

Copy
//inspiration: https://www.hackerrank.com/topics/digit-dp
#include <iostream>
#include <cstdio>
#include <cstring>
 using namespace std;

#define int long long 
const int mod=1e9+7;

int dp[10005][2][105],n,d;


int solve(string s,int idx,bool smaller,int rem)
{
  if(idx==s.size())
  {
    return (rem!=0)?0:1;
  }
  if(dp[idx][smaller][rem]!=-1)
    return dp[idx][smaller][rem];

  int limit=9;
  if(smaller)
    limit=s[idx]-'0';

  int cnt=0;
  
  for(int i=0;i<=limit;i++)
  {
    bool smflag;
    if(i<(s[idx]-'0'))
      smflag=0;
    else
      smflag=smaller;

    cnt=(cnt % mod + solve(s,idx+1,smflag,(rem+i) % d) % mod) % mod;
  }

  return dp[idx][smaller][rem]=cnt;
}

int32_t main()
{
  string s;
  cin>>s>>d;
  n=s.size();
  if(d>9*n)
  {
    cout<<0; exit(0);
  }

  memset(dp,-1,sizeof(dp));

  int ans=solve(s,0,1,0);

  cout<<(ans+mod-1)%mod;

  return 0;  
}   

Submission Info

Submission Time
Task S - Digit Sum
User nilesh8757
Language C++14 (GCC 5.4.1)
Score 0
Code Size 941 Byte
Status

Test Cases

Set Name Score / Max Score Test Cases
All 0 / 100 0_00, 0_01, 0_02, 1_00, 1_01, 1_02, 1_03, 1_04, 1_05, 1_06, 1_07, 1_08, 1_09, 1_10, 1_11, 1_12, 1_13, 1_14, 1_15, 1_16, 1_17, 1_18, 1_19, 1_20, 1_21
Case Name Status Exec Time Memory
0_00 6 ms 16640 KB
0_01 6 ms 16640 KB
0_02 6 ms 16640 KB
1_00 6 ms 16640 KB
1_01 1 ms 256 KB
1_02 196 ms 116272 KB
1_03
1_04
1_05
1_06
1_07
1_08
1_09
1_10
1_11
1_12
1_13
1_14
1_15
1_16
1_17
1_18
1_19
1_20 6 ms 16640 KB
1_21 6 ms 16640 KB