Original link: https://www.shuizilong.com/house/archives/codeforces-round-831/
meaning of the title
You are given a repeatable set $A$ with $n$ elements, each element of the set $A$ is a one-element set ${a_i}$.
Defining an operation consists of the following two steps:
- Select the two sets $S$, $T$ in $A$ whose intersection is empty.
- Remove both sets and add their union to $A$.
After that, we construct a reconfigurable set $M$ that represents the size of all the remaining sets currently.
You can perform any number of operations to ask for the total of all distinct $M$.
practice
If the initial elements are different from each other, it is clear that the original problem is equivalent to the number of splits, although the original problem is given in a merged manner.
Then the original problem is equivalent to the number of splits with some restriction that some elements must be split between them.
Splitting Numbers We know that there are many advanced practices. . . For example, Euler pentagon numbers, generating functions and so on. . . . But this question $n$ is only 2000, and it is unlikely to be used.
Consider the most naive DP with the number of splits. . . We sort the split results in descending order. . Then each case uniquely corresponds to a monotonically decreasing sequence whose sum is n.
dp[i][s][j]: The number of solutions with the sum of s and the end of j at the first i positions currently under investigation.
Have:
const int N = int(1e3) + 9; int dp[2][N][N]; int n; int main() { #ifndef ONLINE_JUDGE //freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif RD(n); int p = 0, q = 1; RST(dp[p]); dp[p][0][n] = 1; REP_1(i, n) { swap(p, q); RST(dp[p]); #define u dp[q][s][j] #define v dp[p][s+k][k] REP(s, n+1) REP(j, n+1) if (u) { DWN_1(k, min(j, ns), 0) v += u; } cout << dp[p][i][0] + 1 << " "; } cout << endl; }
This DP can be optimized to $O(n^3)$ with partial sums.
dp[i][s][j]: The number of solutions with the sum s and the end >= j for the first i positions currently under investigation.
const int N = int(1e3) + 9; int dp[2][N][N]; int n; int main() { #ifndef ONLINE_JUDGE //freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif RD(n); int p = 0, q = 1; RST(dp[p]); dp[p][0][n] = 1; REP_1(i, n) { swap(p, q); RST(dp[p]); #define u dp[q][s][j] #define v dp[p][s+j][j] REP(s, n+1) DWN(j, n+1, 0) u += dp[q][s][j+1]; REP(s, n+1) REP(j, n+1) if (u) v += u; cout << dp[p][i][0] + 1 << " "; } cout << endl; }
Continue to examine restrictions. . . The conclusion is. . . It is equivalent to $s \leq \sum \min(i, c)$
where $c$ iterates over the number of occurrences of each element in the initial set. . .
This conclusion is really not obvious. . . Feelings need to use conjugated properties + various induction yy to come out. . .
So adding the above restrictions as pruning can run O(n2logn). . .
But we know that the naive dp of the split number can be further optimized to $O(n2)$. . .
The reason is that the difference number itself is more special. . . State can be further simplified. . .
This article is reproduced from: https://www.shuizilong.com/house/archives/codeforces-round-831/
This site is for inclusion only, and the copyright belongs to the original author.