LC 3317. 安排活动的方案数

https://leetcode.cn/problems/find-the-number-of-possible-ways-for-an-event/description/

拆解成为下面几个问题

最后选择了i个节目的话，那么评分组合可以有 \(y^i\) 种可能
选择i个节目的组合数量是 \(C(x, i)\)
最后的问题就是将n个人分配到i个节目，并且确保每个节目至少有一个人的可能性是多少

假设这个函数是\(F(n,i)\).

如果随机分配的话，那么可以有 \(i^n\) 种可能性，但是某些节目可能是空
x个节目是空数量是 \(F(n,i-x) * C(i,x)\).
枚举所有x的可能性，这样计算每个 \(F(n,i)\) 的时间复杂是O(N)

class Solution:
    def numberOfWays(self, n: int, x: int, y: int) -> int:

        def dfs(i, prog):
            ans = 0
            if i == n:
                print(prog, y ** len(prog))
                return y ** len(prog)
            for j in range(x):
                prog[j] += 1
                ans += dfs(i + 1, prog)
                prog[j] -= 1
                if prog[j] == 0:
                    del prog[j]
            return ans

        # from collections import Counter
        # return dfs(0, Counter())

        # sum{i=0..x}(y ** i * C(x, i) * F(n, i))
        # F(n, i) 把n个人配置到i个项目里面，并且至少去确保每个都存在一个
        # F(n, i) = (i**n) - F(n,i-1)*C(i,i-1) - F(n,i-2)*C(i,i-2)....
        # F(n, 1) = 1
        MOD = 10 ** 9 + 7

        # a ^ b
        def pow(a, b):
            ans = 1
            t = a
            while b:
                if b & 0x1:
                    ans = (ans * t) % MOD
                t = (t * t) % MOD
                b = b >> 1
            return ans

        C = [[0] * (x + 1) for _ in range(x + 1)]
        C[0][0] = 1
        for i in range(1, x + 1):
            for j in range(0, i + 1):
                C[i][j] = C[i - 1][j] + (C[i - 1][j - 1] if j > 0 else 0)
                C[i][j] %= MOD

        F = [0] * (x + 1)
        F[1] = 1
        for i in range(2, x + 1):
            acc = 0
            for j in reversed(range(i)):
                acc += (F[j] * C[i][j]) % MOD
                acc = acc % MOD
            F[i] = (pow(i, n) - acc) % MOD

        ans = 0
        for i in range(0, x + 1):
            r = pow(y, i) * C[x][i] * F[i]
            # print(i, r, '===>', pow(y, i), C[x][i], F[i])
            ans = (ans + r) % MOD
        return ans