Submission #4000647

Source Code Expand

Copy
#include<bits/stdc++.h>
using namespace std;
#define crap ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
typedef long long int ll;
typedef unsigned long long ull;
typedef std::vector<int> vi;
typedef std::vector<ll> vll;
typedef std::vector<vi > vvi;
typedef std::vector<vll > vvll;
typedef std::pair<int,int> ii;
typedef std::pair< ll, ll > lp;
typedef std::vector<ii> vii;
typedef std::vector<vii > vvii;


#define pb push_back 
#define PB pop_back
#define pf push_front
#define PF pop_front
#define mp make_pair
#define ub(a,b) upper_bound(all(a),b)
#define lb(a,b) lower_bound(all(a),b)
#define bs(a,b) binary_search(all(a),b)
#define mem(a,b) memset(a,b,sizeof(a))
#define in(a,n) f(i,0,n-1)cin>>a[i]
#define in1(a,n) f(i,1,n)cin>>a[i]
#define out(a,n) f(i,0,n-1)cout<<fixed<<setprecision(20)<<a[i]<<" ";cout<<"\n"
#define ff first
#define ss second
#define f(i,a,b) for (int i=a;i<=b;i++)
#define rf(i,a,b) for(int i=a;i>=b;i--)
#define rep(i,n) f(i,0,n-1)
#define clr(a) (a).clear()
#define rz resize
#define sqr(a) ((a) * (a))
#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin() ,(a).rend()
#define endl '\n'

const int M=(int)1e9+7;

string num;
int n,d;

ll dp[1005][2][9055][2];
bool vis[1005][2][9055][2];

ll go(int pos, int f, int sum, int start)
{
	if (pos==n)
	{
		if (sum%d==0 && sum > 0LL)
			return 1;
		else
			return 0;
	}

	ll &ans=dp[pos][f][sum][start];

	if (vis[pos][f][sum][start])
		return ans;

	vis[pos][f][sum][start]=true;
	ans=0LL;

	int LMT=(f)? 9 : num[pos]-'0';

	if (!start)
	{
		f(i,0,LMT)
		{
			int nf=1;
			if (f==0 && i==LMT)nf=0;
			ans=(ans+go(pos+1,nf,sum+i,start))%M;
		}
	}
	else
	{
		f(i,1,LMT)
		{
			int nf=1;
			if (f==0 && i==LMT)nf=0;
			ans=(ans+go(pos+1,nf,sum+i,0))%M;
		}
		ans=(ans+go(pos+1,1,sum,1))%M;
	}

	return ans;


} 

int main(int argc, char const *argv[])
{
	crap;
	cin>>num;
	n=num.length();
	cin>>d;
	cout<<go(0,0,0,1)<<endl;
	return 0;
}

Submission Info

Submission Time
Task S - Digit Sum
User eulerkochy
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2064 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 1 ms 2304 KB
0_01 2 ms 4480 KB
0_02 3 ms 8576 KB
1_00 2 ms 2304 KB
1_01 2 ms 2304 KB
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 2 ms 4480 KB
1_21 2 ms 4480 KB