Advertisement
Josif_tepe

Untitled

Nov 7th, 2022
834
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.80 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstring>
  3. #include <fstream>
  4. using namespace std;
  5. int r, x, n, b;
  6. long long dp[55][55][15];
  7. const long long MOD = 1e9 + 7;
  8. long long rec(int r1, int x1, int b1){
  9. if(b1==1){
  10.         if(r1*x1>=b){
  11.     return 1;
  12.  }
  13.     return 0;
  14. }
  15. if(dp[x1][r1][b1]!=-1){
  16.     return dp[x1][r1][b1];
  17. }
  18.     long long result=0;
  19. for(int i=1; i<r1; i++){
  20.     if(i*x1>=b){
  21.         result+=rec(r1-i, x1, b1-1)*2;
  22.         result %= MOD;
  23.     }
  24. }
  25. for(int j=1; j<x1; j++){
  26.     if(j*r1>=b){
  27.         result+=rec(r1, x1-j, b1-1)*2;
  28.         result %= MOD;
  29.     }
  30. }
  31. return dp[x1][r1][b1]=result;
  32.  
  33.  
  34. }
  35.  
  36.  
  37. int main()
  38. {
  39. //    ifstream cin("input.txt");
  40. int t=0;
  41. cin>>t;
  42. for(int i=0; i<t; i++){
  43. cin>>r>>x>>b>>n;
  44. memset(dp, -1, sizeof dp);
  45. cout<<rec(r, x, n)<<endl;
  46. }
  47.  
  48.  
  49.  
  50.     return 0;
  51. }
  52.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement