c++ - 如何计算将 n 个不同的球涂成恰好 c 种不同颜色的方法？

Question

我最近遇到了一个问题。

假设 f(n,c) = 将 n 个不同的球涂成恰好 c 种不同颜色的方法。 (注意所有c种颜色必须至少使用一次，并且每个球都被认为是不同的)

对于这个问题，我需要计算所有 f(n,c) where 1<=c<=n<=S mod 1e9+7.

对于原始问题，S=200。所以我做了一个 O(S^3) 的解决方案，如下所示:

typedef long long ll;
ll MOD=1e9+7;
#define S 200
ll C[S+2][S+2],pows[S+2][S+2],sel[S+2][S+2];
ll sel_(int n,int c)
{
    ll ans=0; int cur=-1;
    for(int i=c;i>=1;i--)
    {
        cur*=-1;
        ans+=cur*pows[i][n]%MOD*C[c][i]%MOD;
        ans%=MOD;
    }
    return ans;
}
int main()
{
    for(int i=0;i<=S;i++)
    {
        C[i][0]=1; pows[i][0]=1;
        for(int j=1;j<=i;j++)
        C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD;
        for(int j=1;j<=S;j++)
        pows[i][j]=pows[i][j-1]*i%MOD;
    }
    sel[0][0]=1;
    for(int i=1;i<=S;i++)
    {
        for(int j=1;j<=i;j++) sel[i][j]=sel_(i,j);
    }
    //the answers are stored in sel
}

但我想可能有一些方法可以在 O(S^2) 中解决它。我怎样才能做到这一点？

Answer 1

这是 inclusion exclusion principle 的典型应用.让我们用 f(n, k) 表示用最多 k 种颜色(在原来的 c 种颜色中)为 n 个球上色的方法数，并用 g(n, k) 用恰好 k 种颜色(在原来的 c 种颜色中)给 n 个球上色的方法数。然后 g(n, k) = f(n, k) - f(n, k - 1) + f(n, k - 2) - ...。计算用最多 k 种颜色给球上色的方法要容易得多，要容易得多 - 事实上，公式非常简单，但我会留给你去弄清楚它是什么。

最后您要查找的数字是 g(n, c)，可以使用上面的公式计算。