Wie berechnet man die Möglichkeiten, n verschiedene Kugeln mit genauen c verschiedenen Farben zu malen?

Question

Ich bin kürzlich auf ein Problem gestoßen.

Angenommen, f (n, c) = die Möglichkeiten, n verschiedene Bälle mit genauen c verschiedenen Farben zu malen. (Achten, dass alle c Farben müssen mindestens einmal verwendet werden und jeder Ball ist anders betrachtet)

Für dieses Problem, ich brauche alle f zu berechnen (n, c) wobei 1 < = c < = n < = S Mod 1e9 + 7.

Für orginal Problem, S = 200. Also machte ich einen O (S^3) Lösung wie unten:

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 
} 

Aber ich nehme an, es könnte einige Möglichkeiten, um es in O zu lösen (S^2). Wie kann ich das erreichen?

Answer 1

Dies ist eine typische Anwendung für die inclusion exclusion principle. Lassen Sie uns durch f(n, k) die Anzahl der Möglichkeiten, n Kugeln mit bis k Farben (aus dem ursprünglichen c Farben) und g(n, k) die Anzahl der Möglichkeiten, n Kugeln mit genau k Farben (aus dem Original c Farben). Dann g(n, k) = f(n, k) - f(n, k - 1) + f(n, k - 2) - .... Es ist sehr viel einfacher, die Bälle mit bis zu k Farben zu färben - in der Tat ist die Formel sehr einfach, aber ich werde es dir überlassen, um herauszufinden, was es ist.

Und schließlich die Nummer, die Sie suchen, ist g (n, c), die mit der obigen Formel berechnet werden kann.