BZOJ2786 Ural1142 Relation

2015.01.13 10:05 Tue| 1 visits oi_2015| 2015_刷题日常| Text

Solution

现在对我而言,考高精度 == 考 python 水平了 233333

另外,这其实也是一道简简单单打表题~

设 $f[i][j]$ 表示将 i 个字母分为 j 个不同的数的方案数。考虑添加一个字母。若和原有字母取值均不同,则答案为 $f[i-1][j-1] * j$ ,否则答案为 $f[i-1][j] * j$。

Code

t = int(raw_input())
ans = [0] * 55
f = [([0] * 55) for i in range(1, 55)]

ans[1] = f[1][1] = 1
for i in range(2, 51):
    for j in range(1, i + 1):
        f[i][j] = f[i-1][j] * j + f[i-1][j-1] * j
        ans[i] += f[i][j]

while(t):
    t = t - 1
    n = int(raw_input())
    print(ans[n])