SRM585 Div1 Medium(500) LISNumber

LISNumber

動的計画法。小さい順にn枚のカードを選んだとき、a[i]≧a[i+1]となるiがちょうどk個になる並べ方の数を覚えておく。これは同じ数字のカードを区別した場合の数なので、最後に数字ごとにその数字のカードの枚数の階乗で割る。法Mが素数ならば、1/x = x^M-2になる。Pythonならば、pow(x,M-2,M)で高速に計算できる。

class LISNumber:
    def count(self, cardsnum, K):
        M = 1000000007
        S = sum(cardsnum)

        if K>S: return 0

        T = [1]+[0]*S
        l = 0
        for c in cardsnum:
            for i in range(c):
                P = T
                T = [0]*(S+1)
                for k in range(S):
                    T[k] = (T[k]+P[k]*(k-i+1))%M
                    T[k+1] = (T[k+1]+P[k]*(l-k+i))%M
                l += 1

        ans = T[K-1]
        for c in cardsnum:
            t = reduce(lambda a,b: a*b%M, range(1,c+1))
            ans = ans*pow(t,M-2,M)%M
        return ans