Untitled

Oct 6th, 2022
506
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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)