HackerRank Ones and Twos problem solution

In this HackerRank Ones and Twos problem solution, You are using at most A number of 1s and at most B number of 2s. How many different evaluation results are possible when they are formed in an expression containing only addition + sign and multiplication * sign are allowed?

Problem solution in Java.

import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Solution {

    static Solution main;

    public class Range implements Comparable<Range> {
        int minPower;
        int maxPower;
        long range;
        public Range(int min , int max , long r) {
            minPower = min;
            maxPower = max;
            range = r;
        }
        public int compareTo(Range r) {
            int comp = new Integer(minPower).compareTo(r.minPower);
            if(comp!=0) {
                return comp;
            }
            return  new Integer(maxPower).compareTo(r.maxPower);
        }
    }

    public static void main(String[] args) {
        main = new Solution();
        long [][] dp = new long[1001][1001];
        long [][] dp1 = new long[1001][1001];
        long [][] dpsum = new long[1001][1001];
        long sp = 1000000007;
        for(int i = 0 ; i < 1001 ; i++) {
            Arrays.fill(dp[i], 0);
        }
        long [] pow2 = new long [32];
        pow2[0] = 1;
        for(int i = 1 ; i <32 ; i++) {
            pow2[i ] = pow2[i-1] * 2;
        }
        dp[1][1] = 1;
        for(int i = 2 ; i < 1001 ; i++) {
            for(int j = 1 ; j <= i ; j++) {
                long temp = 0;
                for(int k = j+1 ; k < i ; k++) {
                    temp += dp[i-j][k];
                    if(temp>=sp) {
                        temp-=sp;
                    }
                }
                if(i==j) {
                    temp++;
                    if(temp>=sp) {
                        temp-=sp;
                    }
                }
                dp[i][j] = temp ;
            }
        }
        for(int k = 0 ; k < 1001 ; k++) {
            Arrays.fill(dp1[k],0);
        }
        for(int i = 0 ; i < 1001 ; i++) {
            dpsum[i][0] = 0;
        }
        for(int i = 0 ; i < 1001 ; i++) {
            for(int j = 1 ; j < 1001 ; j++) {
                dpsum[i][j] = dpsum[i][j-1] + dp[i][j];
                if(dpsum[i][j]>=sp) {
                    dpsum[i][j] -= sp;
                }
            }
        }
        for(int k = 1 ; k < 1001 ; k++) {
            for(int i = k ; i < 1001 ; i++) {
                if(i==k) {
                    dp1[i][k] = 1;
                } else {
                    dp1[i][k] = dp1[i-1][k] + dp[i][k];
                    if(dp1[i][k] >= sp) {
                        dp1[i][k] -= sp;
                    }
                }
            }
        }
        long [][][] list = new long[1001][32][32];
        long [] all = new long[1001];
        for(int i = 0 ; i < 1001 ; i++) {
            for(int j = 0 ; j < 32 ; j++) {
                for(int k = 0 ; k < 32 ; k++) {
                    list[i][j][k] = 0;
                }
            }
            all[i] = 0;
            for(int j = 1 ; j <= Math.min(i/2, 500) ; j++) {
                for(int k = j + 1 ; k <= i-j ; k++) {
                    long repValue = 0;
                    if(j+k==i) {
                        repValue ++;
                    }
                    repValue += dpsum[i-j-k][i-j-k] - dpsum[i-j-k][k];
                    if(repValue<0) {
                        repValue += sp;
                    }
                    if(repValue>=sp) {
                        repValue -= sp;
                    }
                    if(k<32) {
                        list[i][j][k] = repValue;
                    } else {
                        all[i] += repValue;
                    }
                }
            }
            all[i] %= sp;
        }
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedOutputStream bos = new BufferedOutputStream(System.out);
        String eol = System.getProperty("line.separator");
        byte[] eolb = eol.getBytes();
        try {
            String str = br.readLine();
            int t = Integer.parseInt(str);
            for(int i = 0 ; i < t ; i++) {
                str = br.readLine();
                int blank = str.indexOf(" ");
                int a = Integer.parseInt(str.substring(0,blank));
                int b = Integer.parseInt(str.substring(blank+1));
                long ans = 0;
                if(b==0) {
                    bos.write(new Long(a).toString().getBytes());
                }else if (a==0){
                    for(int d = 0 ; d <= b ; d++) {
                        long temp = dp1[b][d];
                        ans += temp;    
                    }
                    ans %= sp;
                    bos.write(new Long(ans).toString().getBytes());
                } else {
                    for(int d = 0 ; d < b ; d++) {
                        long temp = dp1[b-1][d];
                        long mult = 2;
                        temp *= mult;
                        ans += temp;    
                    }
                    ans %= sp;
                    for(int d = 0 ; d < 32 ; d++) {        
                        for(int e = d+1 ; e < 32 ; e++ ) {
                            long repValue = list[b][d][e];
                            long temp = repValue * Math.min(a+1,pow2[e]-pow2[d]);
                            ans += temp;
                            ans %= sp;
                        }
                    }
                    ans %= sp;
                    long temp = all[b] * (a+1);
                    ans += temp;
                    ans+=a+2;
                    ans %= sp;
                    bos.write(new Long(ans).toString().getBytes());
                }
                bos.write(eolb);
            }
            bos.flush();
        } catch(IOException ioe) {
            ioe.printStackTrace();
        }
    }

}

Problem solution in C++.

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
const int MOD = 1e9 + 7;
int dp_sum[1001][1001],dp_bit[1001][1001];
void add(int &x,long long v){
    v%=MOD;
    x+=v;
    if(x>=MOD)x-=MOD;
}
int f_bit(int lv,int B);
int f_sum(int lv,int B){
    if(lv>B)return 1;
    if(dp_sum[lv][B]!=-1)return dp_sum[lv][B];
    int tmp=f_sum(lv+1,B);
    add(tmp,f_bit(lv,B));
    return dp_sum[lv][B]=tmp;

}
int f_bit(int lv,int B){
    if(lv>B)return 0;
    if(dp_bit[lv][B]!=-1)return dp_bit[lv][B];
    return dp_bit[lv][B]=f_sum(lv+1,B-lv);
}
int main(){
    int T,A,B;
    scanf("%d",&T);
    memset(dp_sum,-1,sizeof(dp_sum));
    memset(dp_bit,-1,sizeof(dp_bit));
    while(T--){
        scanf("%d%d",&A,&B);
        int an=0;
        if(A==0)an=f_sum(1,B);
        else{
            int k=1;
            while((1LL<<k)<=A)k++;
            k++;
            add(an,(long long)(A+1)*f_sum(k,B));
            long long ha=(1LL<<k)-A-1;
            int now=0,i=1;
            long long last=0;
            while(ha>0){
                now++;
                if(B<now)break;
                add(an,min((1LL<<i)-last,ha)*f_sum(k,B-now));
                ha-=(1LL<<i)-last;
                last=1LL<<i;
                i++;
                if(i==k){
                    last=0;
                    i=1;
                }
            }
            /*
            long long last=A;
            for(int i=1;i<=B;i++){
                if(last+1>=(1LL<<k))break;
                add(an,(min(((long long)A+(1LL<<i)),(1LL<<k)-1)-last)*f_sum(k,B-i));
                last=min((long long)A+(1LL<<i),(1LL<<k)-1);
            }*/
        }
        printf("%dn",(an+MOD-1)%MOD);
    }
    return 0;
}

Problem solution in C.

#include <stdio.h>
#include <stdlib.h>
#define MOD 1000000007
long long dp[1001][1001][31]={0},dp3[1001];

int main(){
  int T,A,B,l,i,j,k;
  long long t,f;
  for(k=0;k<31;k++)
    for(i=k+1;i<=1000;i++)
      for(j=k+1;j<=1000;j++)
        if(i==k+1){
          if(j==k+1)
            dp[i][j][k]=1;
        }
        else{
          dp[i][j][k]=dp[i-1][j][k];
          if(j>i)
            dp[i][j][k]=(dp[i][j][k]+dp[i-1][j-i][k])%MOD;
          if(i==j)
            dp[i][j][k]=(dp[i][j][k]+1)%MOD;
        }
  scanf("%d",&T);
  while(T--){
    scanf("%d%d",&A,&B);
    i=A;
    for(k=0;i;i>>=1,k++);
    for(i=0,t=1;i<k+1;i++,t<<=1);
    dp3[0]=(A+1)%MOD;
    l=1;
    for(i=f=1,j=2;i<=k && i<=B;i++,j<<=1,l=i)
      if(j+A<t)
        dp3[i]=(j+A+1)%MOD;
      else{
        dp3[i]=t%MOD;
        f=0;
        l=i+1;
        break;
      }
    if(f){
      f=((j>>1)&0x7fffffff);
      for(i=1,j=2;i<=k-1 && i+k<=B;i++,j<<=1,l=i+k)
        if(j+f+A<t)
          dp3[i+k]=(j+f+A+1)%MOD;
        else{
          dp3[i+k]=t%MOD;
          l=i+k+1;
          break;
        }
    }
    for(;l<1001;l++)
      dp3[l]=dp3[l-1];
    for(i=k+1,t=dp3[1000];i<=B;i++)
      t=(t+dp[B][i][k]*dp3[B-i])%MOD;
    printf("%lldn",(t-1+MOD)%MOD);
  }
  return 0;
}