Advertisement
AntonGorokhov

Untitled

Oct 6th, 2022
506
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.91 KB | None | 0 0
  1. n = (int) (input())
  2.  
  3. if(n%2 == 1) :
  4.     print(0)
  5. else :
  6.     n2 = (int) (n/2)
  7.     dp = [0] * (n2 + 1)
  8.      
  9.     for i in range(n2+1):
  10.         dp[i] = [0] * (n2*9 + 1)
  11.          
  12.     for i in range(n2+1):
  13.         for j in range(n2*9 + 1):
  14.             dp[i][j] = [0]*10
  15.              
  16.     prefix = [0] * (n2 + 1)
  17.      
  18.     for i in range(n2+1):
  19.         prefix[i] = [0] * (n2*9 + 1)
  20.      
  21.     for i in range (10):
  22.         dp[1][i][i] = 1
  23.         prefix[1][i] = 1
  24.          
  25.     for length in range(2, n2 + 1, 1):
  26.         for sum in range (length * 9 + 1):
  27.             for last_num in range (10):
  28.                 if(sum - last_num >= 0):
  29.                     dp[length][sum][last_num] = prefix[length-1][sum-last_num]
  30.                     prefix[length][sum] += dp[length][sum][last_num]
  31.      
  32.     ans = 0
  33.     for sum in range (n2*9 + 1):
  34.         ans += (prefix[n2][sum]*prefix[n2][sum])
  35.      
  36.     print(ans)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement