SHARE
TWEET

CHEFFA Solution

a guest Aug 18th, 2017 79 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define rep(i,n) for(int i=0;i<n;i++)
  5. #define mod 1000000007
  6.  
  7. ll a[131][131];
  8. ll mat[51][131][131];
  9. int arr[50],n;
  10.  
  11. ll find(int i, int j) {
  12.   if(i>j) return a[j][j];
  13.   else return a[i][j];
  14. }
  15.  
  16. ll findAns(int level, ll firstNum, ll secondNum) {
  17.   if(level == n-2) {
  18.     return a[firstNum][secondNum];
  19.   }
  20.   else if(mat[level][firstNum][secondNum] != -1) {
  21.     return mat[level][firstNum][secondNum];
  22.   }
  23.   else {
  24.     ll ans = 0;
  25.     rep(k,min(firstNum,secondNum)+1) ans += findAns(level+1,secondNum-k,arr[level+2]+k)%mod;
  26.     ans %= mod;
  27.     mat[level][firstNum][secondNum] = ans;
  28.     return ans;
  29.   }
  30. }
  31.  
  32. int main() {
  33.   rep(i,131) rep(j,131) a[i][j] = 1;
  34.   rep(i,131) rep(j,131) {
  35.     ll ans = 0;
  36.     rep(k,min(i,j)+1) ans += find(j-k,k)%mod;
  37.     a[i][j] = ans%mod;
  38.   }
  39.  
  40.   int t;
  41.   cin>>t;
  42.   rep(_,t) {
  43.     rep(level,51) rep(i,131) rep(j,131) mat[level][i][j] = -1;
  44.     cin>>n;
  45.     rep(i,n) cin>>arr[i];
  46.     if(n == 1) {
  47.       cout<<1<<'\n';
  48.     }
  49.     else {
  50.       cout<<findAns(0,arr[0],arr[1])<<'\n';
  51.     }
  52.   }
  53.   return 0;
  54. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top