How many ways I can put r1 (same) balls with color 1 , r2 balls with color 2 , ..., rp balls with color p in q different boxes with sizes s1,**s2**,..,**sq** ?
note : r1+r2...+rp=s1+s2+...+sq=N
note 2: N<=1000
I don't have a good algorithm to solve this problem .
| # | User | Rating |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3382 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | heuristica | 3322 |
| 10 | maroonrk | 3312 |
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 144 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | adamant | 137 |
| 8 | BledDest | 133 |
| 9 | maroonrk | 132 |
| 10 | Proof_by_QED | 131 |
maby, dynamic O(n*n) and CRT?
mabyormay be?I think there are N! / (Product_i r_i! * Product_i s_i!) ways.
Sorry, the formula is wrong. Am I right that we can distinguish every pair of boxes?
What is the origin of this problem? How much can be p and q?
I know exponential solution which works for n~50-60, based on Burnside's lemma..
Could you suggest what do you mean by set and group in lemma?
And there is dp in O(p*q*n*binomial(p+q,p))
I don't know about p and q. :) could you please give me some hint about dp.
Please answer from where this problem is first :)
It's my homework. I don't know what's the source.
Hm, maybe you know some related theory? Because I don't know how to solve it with n up to 1000..
it's all about counting and I don't know any idea too. :(
If it's homework, there are some other tasks like this one. Could you give us some examples? Maybe, after it, we will understand, which methods to use...
counting number of ways to put distinguishable/indistinguishable balls in distinguishable/indistinguishable boxes and one of most related problems is this problem without limitation on size of boxes but I think this problem is far different from these.