Timeline for Sum of the sum of all possible subsets raised to power k
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 6, 2023 at 0:30 | history | edited | loopy walt | CC BY-SA 4.0 |
added 288 characters in body
|
| Nov 6, 2023 at 0:17 | comment | added | loopy walt | @Bubbler, technically you are correct, but when the binomial coefficients and powers are lined up binomial-theroem neatly as they are here we can (in principle) compute each from the one before in constant time (ignoring bit length), right? I'll clarify. | |
| Nov 6, 2023 at 0:06 | history | edited | loopy walt | CC BY-SA 4.0 |
deleted 26 characters in body
|
| Nov 6, 2023 at 0:04 | comment | added | Bubbler |
comb(n,j) takes time linear in min(j, n-j), so [comb(n,j) % M for j in range(n+1)] takes \$O(n^2)\$ time (ignoring the bit length of the outputs of comb(n,j)). The list can be precomputed in \$O(n \log n)\$ time via Fermat's theorem. pow(a, j, M) takes \$O(\log j)\$ time as well.
|
|
| Nov 5, 2023 at 23:38 | history | edited | loopy walt | CC BY-SA 4.0 |
added 896 characters in body
|
| Nov 5, 2023 at 23:06 | history | answered | loopy walt | CC BY-SA 4.0 |