I Have Tried the following problem using Digit DP please tell me how to apply memoization to it
Your code here...
#include<iostream>
#include<vector>
#define Mod 1000000007
#define ll long long
using namespace std;
int a,b,n;
bool check_good(int digit_sum){
bool res=1;
while(digit_sum>0){
if(digit_sum%10!=a && digit_sum%10!=b){
res=0;
break;
}
digit_sum/=10;
}
return res;
}
vector<int > num;
ll call(int pos,int digit_sum){
if(pos==n){
if(check_good(digit_sum)){
return 1;
}
else{
return 0;
}
}
ll ans=0;
ans=(ans+call(pos+1,digit_sum+a))%Mod;
ans=(ans+call(pos+1,digit_sum+b))%Mod;
return ans;
}
int main(){
cin>>a>>b>>n;
cout<<call(0,0);
return 0;
}
public void run() { InputReader sc = new InputReader(System.in); //Scanner sc=new Scanner(System.in); // Random sc=new Random(); PrintWriter out = new PrintWriter(System.out);
int a=sc.nextInt(); int b=sc.nextInt(); int n=sc.nextInt(); long fact[]=new long[1000001]; fact[0]=1; long mod=1000000007; for (int i = 1; i <1000001 ; i++) { fact[i]=(fact[i-1]*i)%mod; } long ans=0; for (int noOfA = 0; noOfA <=n ; noOfA++) { int noOfB=n-noOfA; if(check(a*noOfA+b*noOfB,a,b)){ ans=(ans+(((fact[n]*modInv(fact[noOfA],mod))%mod)*modInv(fact[noOfB],mod))%mod)%mod; } } out.println(ans); out.close(); } boolean check(int n,int a,int b){ while (n>0){ if(n%10==a || n%10==b){ n/=10; } else{ return false; } } return true; }Thanks for combinatorics solution !! So Shall I assume that this problem couldn't be solved using DigitDP ? and combinatorics is the only way to solve it
you can use HashMap in java but it takes O(n*MAX_SUM) and it will time out