Advertisement
SuitNdtie

o59_oct_c1_staying

Oct 7th, 2019
168
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.94 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int ll;
  4.  
  5. ll arr[3];
  6. ll const mod = 1e9+7;
  7.  
  8. ll dp[1010][3][8];
  9.  
  10. ll cal(ll n,ll I,int bit){
  11.     if(n == 1){
  12.         bit |= (1<<I);
  13.         if(bit == 7)return 1;
  14.         return 0;
  15.     }
  16.     if(dp[n][I][bit] != -1)return dp[n][I][bit]%mod;
  17.    
  18.    
  19.     ll sum = 0;
  20.     if(arr[I] >= n){
  21.         if((bit|(1<<I))==7)
  22.         sum += 1;
  23.     }
  24.     for(ll i = 1 ; i <= arr[I] ; i ++){
  25.         if(i >= n)break;
  26.         if(I == 0){
  27.             sum = (sum + cal(n-i,2,bit|1)%mod + cal(n-i,1,bit|1)%mod)%mod;  
  28.         }
  29.         else if(I == 1){
  30.             sum = (sum + cal(n-i,2,bit|2)%mod)%mod;
  31.         }
  32.         else if(I == 2){
  33.             sum = (sum + cal(n-i,0,bit|4)%mod)%mod;
  34.         }
  35.     }
  36.     return dp[n][I][bit] = sum%mod;
  37. }
  38.  
  39. int main()
  40. {
  41.     for(int i = 0 ; i < 1010 ; i ++)for(int j = 0 ; j < 3 ; j ++)for(int k = 0 ; k < 8 ; k ++)dp[i][j][k] = -1;
  42.     ll n;
  43.     scanf("%lld",&n);
  44.     scanf("%lld %lld %lld",&arr[0],&arr[1],&arr[2]);
  45.     printf("%lld",cal(n,0,0)%mod);
  46.     return 0;
  47. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement