at3107

Untitled

Sep 21st, 2020
682
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. int dp[1001][1001][2],M=1e9+7;
  2. int help(int ind,int k,bool ok,int n)
  3. {
  4.     if(ind==n) return k==0;
  5.     if(k<0) return 0;
  6.     if(dp[ind][k][ok]==0)
  7.     {
  8.         int x=1;
  9.         if(ok)
  10.         {
  11.             x+=help(ind+1,k,0,n),x%=M;
  12.         }
  13.         else
  14.         {
  15.           x+=help(ind+1,k,0,n),x%=M;
  16.           x+=2*help(ind+1,k-1,1,n),x%=M;
  17.           x+=help(ind+1,k-2,1,n),x%=M;
  18.         }
  19.         dp[ind][k][ok]=x;
  20.     }
  21.     return dp[ind][k][ok]-1;
  22. }
  23. int fun(int n,int k)
  24. {
  25.     int ans=0;
  26.     ans=((help(1,k,0,n)+2*help(1,k-1,1,n))%M+help(1,k-2,1,n))%M;
  27.     return ans;
  28. }
  29.  
RAW Paste Data