taklo's blog

Help How To apply memoization to this DIGIT-DP Code
By taklo, history, 5 years ago, In English

I Have Tried the following problem using Digit DP please tell me how to apply memoization to it

--- Problem Link ---

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;
}
  • Vote: I like it
  • -10
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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;
}
→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      you can use HashMap in java but it takes O(n*MAX_SUM) and it will time out

      → Reply