Problem:


Combination of Number Sequences

0 から 9 までの整数を使った n 個の数の並び k1, k2, ..., kn を考えます。正の整数 n と s を読み込んで、

k1 + 2 &times; k2 + 3 &times; k3 + ... + n &times; kn = s 

となっているような n 個の数の並びが何通りあるかを出力するプログラムを作成してください。ただし、1 つの「n 個の数の並び」には同じ数が 2 回以上現われないものとします。

Input

入力は複数のデータセットからなります。各データセットとして、n (1 ≤ n ≤ 10) と s (0 ≤ s ≤ 10,000)が空白区切りで１行に与えられます。

データセットの数は 100 を超えません。

Output

データセットごとに、n 個の整数の和が s になる組み合わせの個数を１行に出力します。

Sample Input

3 10
3 1

Output for the Sample Input

8
0



Sample input:
3 10
3 1


Sample output:
8
0

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0070
"""
import sys
import time
from itertools import permutations


def solve1(pick, target):
    # ????´???????????????????
    # ??????????????°????????°????¢?????????¨?????????????????°????????????????¢???????????????§???????????????????????????
    hit = 0                     #  ?????¶??????????????????????????°
    for nums in permutations([0, 1, 2, 3, 4, 5, 6, 7, 8, 9], pick): #  ??¨????????°?????????pick????????°?????????????????????????????????
        temp = []
        #  ?????????????????????????????????n=1?????????????????????????????????eval??§????¨????????¨??????????
        for i in range(1, pick+1):
            temp.append('{} * {}'.format(i, nums[0]))
            nums = nums[1:]
        exp = ' + '.join(temp)
        ans = eval(exp)
        if ans == target:
            # print(exp)
            hit += 1
    return hit


def solve2(pick, target):
    # ????????§??????????????£???????????§?????????????????§???????????????
    # 10?????\?????????????????£??????????????????????????????40.0[s]??\???????????£??????????????§?????????????????§????????????????????????
    if target > 330:
        return 0
    hit = 0
    for nums in permutations([0, 1, 2, 3, 4, 5, 6, 7, 8, 9], pick):
        ans = 0                 #  n??????????????§???????¨????
        for i in range(1, pick+1):
            ans += (i * nums[i-1])
            if ans > target:    #  ????¨???????????????????????????¨????????\????¶???????????????¶????????????????????§??????????????§???????????????
                break
        if ans == target:
            hit += 1
    return hit


def solve3(pick, target):
    # zip()????????¨?????????????????????
    if target > 330:
        return 0
    hit = 0
    for nums in permutations([0, 1, 2, 3, 4, 5, 6, 7, 8, 9], pick):
        temp = [x * y for x, y in zip(nums, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10])]
        ans = sum(temp)
        if ans == target:
            hit += 1
    return hit


def calc_min_max(pick, numbers):
    # ?????????????????°???????????¨??????pick????????°????????????????????????????°????????????§????????????
    multiplier = range(1, pick+1)
    min_numbers = numbers[:pick]
    min_numbers.sort(reverse=True)
    temp = [x*y for x, y in zip(min_numbers, multiplier)]
    min = sum(temp)

    numbers = numbers[-pick:]
    temp = [x*y for x, y in zip(numbers, multiplier)]
    max = sum(temp)

    return min, max


def solve4(pick, target, numbers=[0,1,2,3,4,5,6,7,8,9]):
    # ??°??????1?????????????????????????????°????????????????????¨?????§??????????¨???????min, max???????¨?????????????
    # ??????????????????????¨?????????°??????????????¨?????§?????????????????????????????°?????§??????????????§??????????????£?????¨????????§????????????????????¢??????????????????
    # 7.72 [s]
    global Hit
    if pick == 0:
        if target == 0:
            Hit += 1
        return

    for n in numbers:
        lnumbers = numbers[:]
        lnumbers.remove(n)
        p_min, p_max = calc_min_max(pick-1, lnumbers)
        if target-(n*pick) > p_max or target-(n*pick) < p_min:
            continue
        else:
            solve4(pick-1, target-(n*pick), lnumbers)


def has_possibility(pick, target, numbers):
    # ?????????????????°???????????¨??????pick????????°????????????????????????????°????????????§???????±???????
    # ???????????°?????????????????????????????????????????????????????????
    if pick == 1:
        return numbers[0] <= target <= numbers[-1]

    multiplier = range(1, pick+1)
    max_numbers = numbers[-pick:] #  ??§??????????????°??????pick????????????
    max = sum(x*y for x, y in zip(max_numbers, multiplier))
    if target > max:
        return False

    min_numbers = numbers[:pick]
    #min_numbers.sort(reverse=True)
    min_numbers.reverse()       #  .sort(reverse=True)?????????????????£????????????
    min = sum(x*y for x, y in zip(min_numbers, multiplier))
    if target < min:
        return False

    return True


Hit = 0
def solve5(pick, target, numbers=[0,1,2,3,4,5,6,7,8,9]):
    # ??°??????1?????????????????????????????°????????????????????¨?????§??????????¨???????min, max???????¨?????????????
    # ??????????????????????¨?????????°??????????????¨?????§?????????????????????????????°?????§??????????????§??????????????£?????¨????????§????????????????????¢??????????????????
    # 4.xx [s]
    global Hit
    if pick == 1:
        if target in numbers:
            Hit += 1
        return

    for n in numbers:
        lnumbers = numbers[:]
        lnumbers.remove(n)
        if has_possibility(pick-1, target-(n*pick), lnumbers):
            solve5(pick-1, target-(n*pick), lnumbers)
        else:
            continue


def main(args):
    global Hit
    for line in sys.stdin:
        pick, target = [int(x) for x in line.strip().split(' ')]
        solve5(pick, target)
        print(Hit)
        Hit = 0

#    solve5(8, 100)
#    print(Hit)
#    Hit = 0
#    solve5(9, 150)
#    print(Hit)
#    Hit = 0


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0070
"""
import sys
import time
from itertools import permutations


def solve1(pick, target):
    # ????´???????????????????
    # ??????????????°????????°????¢?????????¨?????????????????°????????????????¢???????????????§???????????????????????????
    hit = 0                     #  ?????¶??????????????????????????°
    for nums in permutations([0, 1, 2, 3, 4, 5, 6, 7, 8, 9], pick): #  ??¨????????°?????????pick????????°?????????????????????????????????
        temp = []
        #  ?????????????????????????????????n=1?????????????????????????????????eval??§????¨????????¨??????????
        for i in range(1, pick+1):
            temp.append('{} * {}'.format(i, nums[0]))
            nums = nums[1:]
        exp = ' + '.join(temp)
        ans = eval(exp)
        if ans == target:
            # print(exp)
            hit += 1
    return hit


def solve2(pick, target):
    # ????????§??????????????£???????????§?????????????????§???????????????
    # 10?????\?????????????????£??????????????????????????????40.0[s]??\???????????£??????????????§?????????????????§????????????????????????
    if target > 330:
        return 0
    hit = 0
    for nums in permutations([0, 1, 2, 3, 4, 5, 6, 7, 8, 9], pick):
        ans = 0                 #  n??????????????§???????¨????
        for i in range(1, pick+1):
            ans += (i * nums[i-1])
            if ans > target:    #  ????¨???????????????????????????¨????????\????¶???????????????¶????????????????????§??????????????§???????????????
                break
        if ans == target:
            hit += 1
    return hit


def solve3(pick, target):
    # zip()????????¨?????????????????????
    if target > 330:
        return 0
    hit = 0
    for nums in permutations([0, 1, 2, 3, 4, 5, 6, 7, 8, 9], pick):
        temp = [x * y for x, y in zip(nums, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10])]
        ans = sum(temp)
        if ans == target:
            hit += 1
    return hit


def calc_min_max(pick, numbers):
    # ?????????????????°???????????¨??????pick????????°????????????????????????????°????????????§????????????
    multiplier = range(1, pick+1)
    min_numbers = numbers[:pick]
    min_numbers.sort(reverse=True)
    temp = [x*y for x, y in zip(min_numbers, multiplier)]
    min = sum(temp)

    numbers = numbers[-pick:]
    temp = [x*y for x, y in zip(numbers, multiplier)]
    max = sum(temp)

    return min, max


def solve4(pick, target, numbers=[0,1,2,3,4,5,6,7,8,9]):
    # ??°??????1?????????????????????????????°????????????????????¨?????§??????????¨???????min, max???????¨?????????????
    # ??????????????????????¨?????????°??????????????¨?????§?????????????????????????????°?????§??????????????§??????????????£?????¨????????§????????????????????¢??????????????????
    # 7.72 [s]
    global Hit
    if pick == 0:
        if target == 0:
            Hit += 1
        return

    for n in numbers:
        lnumbers = numbers[:]   #  ??????????????¨??§????????°???????????????????????§.remove()???????????§?????????????????????????????????????????????
        lnumbers.remove(n)
        p_min, p_max = calc_min_max(pick-1, lnumbers)
        if target-(n*pick) > p_max or target-(n*pick) < p_min:
            continue
        else:
            solve4(pick-1, target-(n*pick), lnumbers)


def has_possibility(pick, target, numbers):
    # ?????????????????°???????????¨??????pick????????°????????????????????????????°????????????§???????±???????
    # ???????????°?????????????????????????????????????????????????????????
    if pick == 1:
        return numbers[0] <= target <= numbers[-1]

    # ?????§????????§??????
    multiplier = range(1, pick+1)
    max_numbers = numbers[-pick:] #  ??§??????????????°??????pick????????????
    max = sum(x*y for x, y in zip(max_numbers, multiplier))
    if target > max:
        return False

    # ????°?????????§??????
    min_numbers = numbers[:pick]
    #min_numbers.sort(reverse=True)
    min_numbers.reverse()       #  .sort(reverse=True)?????????????????£????????????
    min = sum(x*y for x, y in zip(min_numbers, multiplier))
    if target < min:
        return False

    return True


Hit = 0
def solve5(pick, target, numbers=[0,1,2,3,4,5,6,7,8,9]):
    # ??°??????1?????????????????????????????°????????????????????¨?????§??????????¨???????min, max???????¨?????????????
    # ??????????????????????¨?????????°??????????????¨?????§?????????????????????????????°?????§??????????????§??????????????£?????¨????????§????????????????????¢??????????????????
    # 4.16 [s]
    global Hit
    if pick == 1:               #  ?????°????????????????????°???1???????´????????????????pick==1???????????§??????????????????
        if target in numbers:
            Hit += 1
        return

    for n in numbers:
        lnumbers = numbers[:]#  ??????????????¨??§????????°???????????????????????§.remove()???????????§?????????????????????????????????????????????
        lnumbers.remove(n)
        if has_possibility(pick-1, target-(n*pick), lnumbers):
            solve5(pick-1, target-(n*pick), lnumbers) #  ??????????????°???????????????????????????????????°????????????


def main(args):
    global Hit
    for line in sys.stdin:
        pick, target = [int(x) for x in line.strip().split(' ')]
        solve5(pick, target)
        print(Hit)
        Hit = 0

#    solve5(8, 100)
#    print(Hit)
#    Hit = 0
#    solve5(9, 150)
#    print(Hit)
#    Hit = 0


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
s_max = [0]
for i in range(1,11):
    s = 0
    for j in range(i):
        s += (10 - j - 1)*(i - j)
    s_max.append(s)

def check(u, r, s, m):
    if r == 0:
        return s == 0
    n = 0
    for i in range(10):
        n *= 2
        if u[i]:
            n += 1
    if (n, r, s) in m:
        return m[(n, r, s)]
    if s < 0 or s > s_max[r]:
        return 0

    ans = 0
    for i in range(10):
        if not u[i]:
            u[i] = True
            ans += check(u, r - 1, s - i*r, m)
            u[i] = False
    m[(n, r, s)] = ans
    return m[(n, r, s)]

memo = {}
while True:
    try:
        n, s = map(int, input().split())
        used = [False for i in range(10)]
        ans = check(used, n, s, memo)
        print(ans)
    except:
        break

Submission status: Accepted

Solution code:
# AOJ 0070 Combination of Number Sequences
# Python3 2018.6.17 bal4u

vmin = [ 0, 0,  1,  4, 10,  20,  35,  56,  84, 120, 165 ]
vmax = [ 0, 9, 26, 50, 80, 115, 154, 196, 240, 285, 330 ]
lim = [ 0, 4, 13, 27, 45,  67,  94, 126, 162, 202, 247 ]
tbl = [ [ 0 ], \
	[ 1, 1, 1, 1, 1 ], \
	[ 1, 2, 1, 3, 3, 3, 4, 5, 4, 5, 5, 4, 5 ], \
	[ 1, 3, 2, 6, 5, 6, 8, 13, 8, 16, 14, 14, 16, 23, 15, 26, 22, 21, 24, 30, 19, 31, 26, 22 ], \
	[ 1, 4, 4, 9, 11, 14, 16, 25, 20, 32, 29, 38, 38, 56, 45, 70, 61, 74, 69, 92, 71, 103, 88, \
	105, 100, 136, 98, 131, 113, 131, 119, 150, 118, 150, 119, 160 ], \
	[ 1, 5, 7, 13, 22, 25, 32, 49, 52, 62, 76, 88, 91, 119, 114, 146, 160, 170, 172, 231, 223, \
	249, 269, 298, 297, 372, 326, 375, 404, 407, 424, 484, 464, 481, 514, 553, 533, 581, 554, 589, 653, \
	597, 601, 657, 630, 647, 660, 643 ], \
	[ 1, 6, 11, 19, 38, 44, 62, 88, 106, 124, 170, 188, 221, 271, 276, 323, 397, 395, 438, 533, \
	544, 568, 687, 694, 769, 861, 893, 942, 1114, 1078, 1180, 1293, 1342, 1351, 1574, 1491, 1640, 1748, \
	1775, 1764, 2029, 1920, 2026, 2162, 2178, 2191, 2430, 2292, 2383, 2552, 2488, 2488, 2709, 2583, 2598, \
	2777, 2618, 2659, 2841, 2657 ], \
	[ 1, 7, 16, 28, 59, 75, 109, 151, 206, 234, 335, 360, 467, 529, 630, 675, 896, 878, 1053, \
	1141, 1340, 1294, 1632, 1571, 1895, 1896, 2184, 2129, 2632, 2485, 2926, 2909, 3356, 3190, 3911, \
	3583, 4259, 4158, 4663, 4477, 5370, 4886, 5622, 5475, 6171, 5776, 6772, 6186, 7073, 6776, 7435, \
	6953, 8178, 7344, 8270, 7927, 8551, 8030, 9184, 8285, 9227, 8758, 9408, 8650, 9937, 8868, 9716, \
	9281, 9870, 9035, 10092 ], \
	[ 1, 8, 22, 40, 83, 122, 173, 248, 350, 408, 575, 669, 842, 963, 1211, 1264, 1652, 1767, \
	2083, 2248, 2752, 2671, 3274, 3352, 3928, 3978, 4624, 4554, 5428, 5384, 6115, 6158, 7195, 6897, 8052, \
	7886, 8928, 8772, 10083, 9670, 11309, 10830, 12110, 11865, 13681, 12871, 14740, 14098, 15900, 15138, \
	17241, 15947, 18464, 17353, 19307, 18345, 20745, 18949, 21681, 20236, 22624, 21027, 23607, 21467, \
	24536, 22553, 24793, 23187, 26012, 23373, 26355, 24094, 26581, 24463, 27187, 24377, 27453, 24768, 27006 ], \
	[ 1, 9, 28, 51, 107, 177, 234, 360, 498, 619, 819, 1040, 1252, 1528, 1824, 2010, 2533, 2837, \
	3180, 3676, 4305, 4493, 5130, 5672, 6156, 6909, 7424, 7830, 8773, 9392, 9892, 10678, 11647, 12141, \
	13026, 13918, 14519, 15611, 16278, 16780, 18686, 19280, 19586, 20795, 22385, 22896, 23948, 24970, \
	26012, 27096, 28467, 28427, 30540, 31272, 31774, 33264, 34748, 34499, 36299, 36596, 38456, 38926, \
	39984, 39386, 42068, 42848, 42424, 42925, 45044, 44584, 46040, 45496, 46890, 47036, 47341, 47646, \
	48887, 48840, 48044, 48540, 50066, 48970, 49062 ] ]

while True:
	try: n, s = list(map(int, input().split()))
	except: break

	if n > 10 or s < vmin[n] or s > vmax[n]: ans = 0
	else:
		if s > lim[n]: s = vmax[n] + vmin[n] - s
		s -= vmin[n]
		if n == 10: n = 9
		ans = tbl[n][s]
	print(ans)

Submission status: Accepted

Solution code:
import sys
dp=[[[0]*331 for i in xrange((1<<10)+1)] for j in xrange(12)]
#dp[12][1025][340]
dp[0][0][0]=1
for i in xrange(10):
    for j in xrange(1<<10):
        for c in xrange(331):
            if dp[i][j][c]==0:
                continue
            for k in xrange(10):
                if (j>>k&1)==0:
                    dp[i+1][j|(1<<k)][(i+1)*k+c]+=dp[i][j][c]
ans=[[0]*331 for unused in xrange(12)]
for i in xrange(11):
    for j in xrange(1<<10):
        for c in xrange(331):
            ans[i][c]+=dp[i][j][c]
for line in sys.stdin.readlines():
    n,s=map(int,line.strip().split())
    if s>330:
        print 0
    else:
        print ans[n][s]

Submission status: Accepted

Solution code:
import sys
dp=[[[0]*331 for i in xrange((1<<10)+1)] for j in xrange(12)]
#dp[12][1025][331]
dp[0][0][0]=1
for i in xrange(10):
    for j in xrange(1<<10):
        for c in xrange(331):
            if dp[i][j][c]==0:
                continue
            for k in xrange(10):
                if (j>>k&1)==0:
                    dp[i+1][j|(1<<k)][(i+1)*k+c]+=dp[i][j][c]
ans=[[0]*331 for unused in xrange(12)]
for i in xrange(11):
    for j in xrange(1<<10):
        for c in xrange(331):
            ans[i][c]+=dp[i][j][c]
for line in sys.stdin.readlines():
    n,s=map(int,line.strip().split())
    if s>330:
        print 0
    else:
        print ans[n][s]

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from __future__ import (division, absolute_import, print_function,
                        unicode_literals)
from sys import stdin

def solve(li, n, s, total, cnt):
    for i in li:
        value = i * n + total
        if value > s:
            break
        if n - 1:
            subli = li[:]
            subli.remove(i)
            r = range(n - 1, 0, -1)
            minimum = value + sum(i * j for i, j in zip(r, subli))
            maximum = value + sum(i * j for i, j in zip(r, subli[::-1]))
            if minimum <= s <= maximum: 
                solve(subli, n - 1, s, value, cnt)
        elif value == s:
            cnt[0] += 1
            break

cnt = [0]
for line in stdin:
    n, s = (int(s) for s in line.split())
    cnt[0] = 0

    solve(list(range(10)), n, s, 0, cnt)
    print(cnt[0])

Submission status: Accepted

Solution code:
import sys
def f0070(A,n,s):
  if n==1:
    if s in A: return 1
    else: return 0
  c=0
  A=sorted(A)
  A1=A[:n][::-1]
  A2=A[-n:]
  N=range(n)
  b1=sum([(i+1)*A1[i] for i in N])
  b2=sum([(i+1)*A2[i] for i in N])
  if s<b1 or s>b2: return 0
  for i in range(len(A)):
    b=s-A[i]*n
    c+=f0070(A[:i]+A[i+1:],n-1,b)
  return c

for a in sys.stdin:
  c=0
  n,s=map(int,a.split())
  c=f0070(range(10),n,s)
  print c

Submission status: Accepted

Solution code:
import sys
def f0070(A,n,s):
  if n==1:return s in A
  c=0
  A=sorted(A)
  A1=A[:n][::-1]
  A2=A[-n:]
  N=range(n)
  def f(A):
    return sum([(i+1)*A[i] for i in N])
  if f(A1)<=s<=f(A2):
    for i in range(len(A)):
      b=s-A[i]*n
      c+=f0070(A[:i]+A[i+1:],n-1,b)
  return c
for a in sys.stdin:
  n,s=map(int,a.split())
  print f0070(range(10),n,s)

Submission status: Accepted

Solution code:
import sys
def f0070(A,n,s):
  if n==1: return (s in A)
  c=0
  A=sorted(A)
  A1=A[:n][::-1]
  A2=A[-n:]
  N=range(n)
  def f(A):
    return sum([(i+1)*A[i] for i in N])
  b1=f(A1)
  b2=f(A2)
  if b1<=s<=b2:
    for i in range(len(A)):
      b=s-A[i]*n
      c+=f0070(A[:i]+A[i+1:],n-1,b)
  return c
for a in sys.stdin:
  n,s=map(int,a.split())
  print f0070(range(10),n,s)

Submission status: Accepted

Solution code:
import sys
def f0070(A,n,s):
  if n==1: return (s in A)
  c=0
  A=sorted(A)
  A1=A[:n][::-1]
  A2=A[-n:]
  N=range(n)
  def f(A):
    return sum([(i+1)*A[i] for i in N])
  if f(A1)<=s<=f(A2):
    for i in range(len(A)):
      b=s-A[i]*n
      c+=f0070(A[:i]+A[i+1:],n-1,b)
  return c
for a in sys.stdin:
  n,s=map(int,a.split())
  print f0070(range(10),n,s)

Submission status: Accepted

Solution code:
import sys
def f0070(A,n,s):
  if n==1:
    if s in A:f=1
    else:f=0
    return f
  c=0
  A=sorted(A)
  A1=A[:n][::-1]
  A2=A[-n:]
  N=range(n)
  def f(A):
    return sum([(i+1)*A[i] for i in N])
  if f(A1)<=s<=f(A2):
    for i in range(len(A)):
      b=s-A[i]*n
      c+=f0070(A[:i]+A[i+1:],n-1,b)
  return c

for a in sys.stdin:
  n,s=map(int,a.split())
  print f0070(range(10),n,s)

Submission status: Accepted

Solution code:
import sys
def f0070(A,n,s):
  if n==1:return s in A
  A=sorted(A)
  A1=A[:n][::-1]
  A2=A[-n:]
  N=range(n)
  b1=0
  b2=0
  c=0
  for i in N:
    b1+=(i+1)*A1[i]
    b2+=(i+1)*A2[i]
  if b1<=s<=b2:
    for i in range(len(A)):
      b=s-A[i]*n
      c+=f0070(A[:i]+A[i+1:],n-1,b)
  return c
for a in sys.stdin:
  n,s=map(int,a.split())
  print f0070(range(10),n,s)

Submission status: Accepted

Solution code:
import sys
def f0070(A,n,s):
  if n==1:return s in A
  A=sorted(A)
  A1=A[:n][::-1]
  A2=A[-n:]
  b1=0
  b2=0
  c=0
  j=1
  for i in range(n):
    b1+=j*A1[i]
    b2+=j*A2[i]
    j+=1
  if b1<=s<=b2:
    for i in range(len(A)):
      c+=f0070(A[:i]+A[i+1:],n-1,s-A[i]*n)
  return c
for a in sys.stdin:
  n,s=map(int,a.split())
  print f0070(range(10),n,s)

Submission status: Accepted

Solution code:
import sys
def f0070(A,n,s):
  if n==1:return s in A
  A=sorted(A)
  b1=0
  b2=0
  c=0
  j=1
  for e,f in zip(A[:n][::-1],A[-n:]):
    b1+=j*e
    b2+=j*f
    j+=1
  if b1<=s<=b2:
    for i in range(len(A)):
      c+=f0070(A[:i]+A[i+1:],n-1,s-A[i]*n)
  return c

for a in sys.stdin:
  n,s=map(int,a.split())
  print f0070(range(10),n,s)

Submission status: Accepted

Solution code:
import sys
K=1024
N=331
R=range(K)
B=[1,2,4,8,16,32,64,128,256,512]
C=[0]*K
D=[[0 for i in range(N)]for j in R]

def init():
  global C,D
  for i in R:
    s=format(i,'b')
    n=s.count('1')
    C[i]=n
    if n==1:D[i][B.index(i)]=1
    else:
      for j in range(len(s)):
        if s[-j-1]=='1':
          dp=n*j
          i2=i-B[j]
          for k in range(N-dp):
            D[i][k+dp]+=D[i2][k]
  return
   
init()
for a in sys.stdin:
  n,s=map(int,a.split())
  x=0
  if s<N:x=sum([D[i][s] for i in R if C[i]==n])
  print x

Submission status: Accepted

Solution code:
import sys
K=1024
N=331
R=range(K)
B=[1,2,4,8,16,32,64,128,256,512]
C=[0]*K
D=[[0 for i in range(N)]for j in R]

for i in R:
  s=format(i,'b')
  n=s.count('1')
  C[i]=n
  if n==1:D[i][B.index(i)]=1
  else:
    for j in range(len(s)):
      if s[-j-1]=='1':
        dp=n*j
        i2=i-B[j]
        for k in range(N-dp):
          D[i][k+dp]+=D[i2][k]
   
for a in sys.stdin:
  n,s=map(int,a.split())
  x=0
  if s<N:x=sum([D[i][s] for i in R if C[i]==n])
  print x

Submission status: Accepted

Solution code:
def mx(ls,m):
	global n
	sum = 0
	for i in range(m):
		sum += (n-i)*ls[-i-1]
	return sum

def mn(ls,m):
	global n
	sum = 0
	for i in range(m):
		sum += (n-i)*ls[i]
	return sum
	
def f(ls,m,s):
	global n
	count = 0
	if m > 0:
		if mx(ls,m) < s or mn(ls,m) > s: return 0
		for i in range(len(ls)):
			lls = ls[:]
			a = (n-m+1)*lls.pop(i)
			if s-a < 0:	break
			else: count += f(lls,m-1,s-a)
		return count
	else:
		return 1 if s == 0 else 0
			
ls = [i for i in range(10)]
while True:
	try:
		n,s = map(int, raw_input().split())
		print f(ls,n,s)
	except:
		break

Submission status: Accepted

Solution code:
def mx(ls,m):
	global n
	sum = 0
	for i in range(m):
		sum += (n-i)*ls[-i-1]
	return sum

def mn(ls,m):
	global n
	sum = 0
	for i in range(m):
		sum += (n-i)*ls[i]
	return sum
	
def f(ls,m,s):
	global n
	count = 0
	if m > 0:
		vmx,vmn = mx(ls,m),mn(ls,m)
		if vmx < s or vmn > s: return 0
		elif vmx == s or vmn == s: return 1
		for i in range(len(ls)):
			lls = ls[:]
			a = (n-m+1)*lls.pop(i)
			if s-a < 0:	break
			else: count += f(lls,m-1,s-a)
		return count
	else:
		return 1 if s == 0 else 0
			
ls = [i for i in range(10)]
while True:
	try:
		n,s = map(int, raw_input().split())
		print f(ls,n,s)
	except:
		break

Submission status: Accepted

Solution code:
def mx(ls,m):
	global n
	sum = 0
	for i in range(m):
		sum += (n-i)*ls[-i-1]
	return sum

def mn(ls,m):
	global n
	sum = 0
	for i in range(m):
		sum += (n-i)*ls[i]
	return sum
	
def f(ls,m,s):
	global n
	count = 0
	if m > 0:
		vmx,vmn = mx(ls,m),mn(ls,m)
		if vmx < s or vmn > s: return 0
		elif vmx == s or vmn == s: return 1
		for i in range(len(ls)):
			lls = ls[:]
			a = (n-m+1)*lls.pop(i)
			if s-a < 0:	break
			else: count += f(lls,m-1,s-a)
		return count
	else:
		return 1 if s == 0 else 0
			
ls = [i for i in range(10)]
while True:
	try:
		n,s = map(int, raw_input().split())
                if mx(ls,n) > 330:
                    print 0
		else: print f(ls,n,s)
	except:
		break

Submission status: Accepted

Solution code:
def mxmn(ls,m):
	global n
	s1,s2 = 0, 0
	for i in range(m):
		s1 += (n-i)*ls[-i-1]
		s2 += (n-i)*ls[i]
	return s1,s2

def f(ls,m,s):
	global n
	count = 0
	if m > 0:
		mx,mn = mxmn(ls,m)
		if mx < s or mn > s: return 0
		elif mx == s or mn == s: return 1
		for i in range(len(ls)):
			lls = ls[:]
			a = (n-m+1)*lls.pop(i)
			if s-a < 0:	break
			else: count += f(lls,m-1,s-a)
		return count
	else:
		return 1 if s == 0 else 0
			
ls = [i for i in range(10)]
while True:
	try:
		n,s = map(int, raw_input().split())
		print f(ls,n,s)
	except:
		break

Submission status: Accepted

Solution code:
import sys
readlines = sys.stdin.readlines
write = sys.stdout.write

def solve():
    for line in readlines():
        N, S = map(int, line.split())
        memo = {}
        def dfs(i, state, rest):
            if i == N:
                return +(rest == 0)
            if rest < 0:
                return 0
            key = (state, rest)
            if key in memo:
                return memo[key]
            r = 0
            for k in range(10):
                if state & (1 << k):
                    continue
                r += dfs(i+1, state | (1 << k), rest - k*(i+1))
            memo[key] = r
            return r
        write("%d\n" % dfs(0, 0, S))
solve()

Submission status: Accepted

Solution code:
max = 0
for i in range(1,10):
    max += i * (i + 1)

dp=[[[-1] * 1025 for i in range(max + 1)] for j in range(11)]

def solve(n,s,used):
    if n == 0 and s == 0:
        return 1;
    if n <= 0 or s < 0:
        return 0
    if dp[n][s][used] != -1:
        return dp[n][s][used]
        
    sum = 0
    for i in range(0,10):
        if (used >> i) % 2 == 0:
            used += 1 << i
            sum += solve(n - 1,s - i * n,used)
            used -= 1 << i
    dp[n][s][used] = sum        
    return sum

while(1):
    try:
        n,s = (int(x) for x in input().split())
        ans = 0
        if s >= 0 and s <= max:
            used = 0
            ans = solve(n,s,used)
        print(ans)
    except:
        break