Cerinta completa

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?

Note that, multiplication takes precedence over addition.

For example, if A=2 and B=2, then we have the following expressions:

  • 1, 1*1 = 1
  • 2, 1*2, 1*1*2, 1+1 = 2
  • 1+2, 1+1*2 = 3
  • 2+2, 2*2, 1+1+2, 1*2*2, 1*1*2*2, 1*2+1*2, 1*1*2+2, 1*2+2 = 4
  • 1+2+2, 1+1*2+2 = 5
  • 1+1+2+2, 1+1+2*2 = 6

So there are 6 unique results that can be formed if A = 2 and B = 2.

Input Format

The first line contains the number of test cases T, T testcases follow each in a newline.
Each testcase contains 2 integers A and B separated by a single space.

Constraints

1 <= T <= 105
0<=A<=1000000000
0<=B<=1000

Output Format

Print the number of different evaluations modulo (%) (109+7.)

Sample Input

4
0 0
2 2
0 2
2 0

Sample Output

0
6
2
2

Explanation

  • When A = 0, B = 0, there are no expressions, hence 0.
  • When A = 2, B = 2, as explained in the problem statement above, expressions leads to 6 possible solutions.
  • When A = 0, B = 2, we have 2, 2+2 or 2*2, hence 2.
  • When A = 2, B = 0, we have 1 or 1*1, 1+1 hence 2.

Limbajul de programare folosit: cpp14

Cod:

#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("%lld\n",(t-1+MOD)%MOD);
  }
  return 0;
}

Scor obtinut: 1.0

Submission ID: 464647754

Link challenge: https://www.hackerrank.com/challenges/ones-and-twos/problem

Ones and Twos