Submission #4000556

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[10005][2][90055][2];
bool vis[10005][2][90055][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 2068 Byte
Status

Compile Error

/tmp/ccKDtAeg.o: In function `go(int, int, int, int)':
Main.cpp:(.text+0x13): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in /tmp/ccKDtAeg.o
Main.cpp:(.text+0x78): relocation truncated to fit: R_X86_64_32S against symbol `dp' defined in .bss section in /tmp/ccKDtAeg.o
Main.cpp:(.text+0x89): relocation truncated to fit: R_X86_64_PC32 against symbol `num' defined in .bss section in /tmp/ccKDtAeg.o
Main.cpp:(.text+0x95): relocation truncated to fit: R_X86_64_32 against symbol `num' defined in .bss section in /tmp/ccKDtAeg.o
Main.cpp:(.text+0xa5): relocation truncated to fit: R_X86_64_PC32 against symbol `num' defined in .bss section in /tmp/ccKDtAeg.o
Main.cpp:(.text+0xe5): relocation truncated to fit: R_X86_64_32S against symbol `dp' defined in .bss section in /tmp/ccKDtAeg.o
Main.cpp:(.text+0xf7): relocation truncated to fit: R_X86_64_32S against symbol `dp' defined in .bss section in /tmp/ccKDtAeg.o
Main.cpp:(.text+0x115): relocation truncated to fit: R_X86_64_PC32 ag...