derangement.py

#!/bin/python2.7

def D(n):
    if n == 0:
        return 1
    if n == 1:
        return 0
    a, b = 1, 0
    for i in range(1, n, 2):
        a = i * (a + b)
        b = (i + 1) * (b + a)    
    return b if n % 2 == 1 else a

def slowD(n):
    if n == 0:
        return 1
    if n == 1:
        return 0
    return (n-1)*(slowD(n-1) + slowD(n-2))

def main():
    print D(10000)

if __name__ == "__main__":
    main()