CF1740F Conditional Mix
The main idea of the topic
has a positive integer
no
no
n and a length of
no
no
sequence of n
a
a
a,
1
≤
a
i
≤
no
1\leq a_i\leq n
1≤ai?≤n.
put each
a
i
a_i
ai? as a unary set
{
a
i
}
\{a_i\}
{ai?}, each time you can merge two collections whose intersection is empty. Can be combined any number of times. After merging the elements of each set, the array composition can be reassembled as
S
S
S, seek
S
S
The number of types of S, the output answer modulo
998244353
998244353
998244353.
1
≤
no
≤
2000
1\leq n\leq 2000
1≤n≤2000
Problem solution
First, we complement the
0
0
0 changes the number of elements in this reset to
no
no
n. It may be advisable to assume that the elements in the reset are from large to small.
For two positions within the reset
i
,
j
i,j
i, j, if the size of the corresponding set is
A
i
A_i
Ai? and
A
j
A_j
Aj? and
A
i
>
A
j
A_i>A_j
Ai?>Aj?, then the set
A
i
A_i
There must be an element in Ai? that can be taken out and put into
A
j
A_j
Aj?. That is, for two resetable
A
A
A and
B
B
B, if satisfied
?
1
≤
k
≤
no
\forall1\leq k\leq n
?1≤k≤n are satisfied
∑
i
=
1
k
A
i
≤
∑
i
=
1
k
B
i
\sum\limits_{i=1}^kA_i\leq \sum\limits_{i=1}^kB_i
i=1∑k?Ai?≤i=1∑k?Bi?, then if
A
A
A is legal, then
B
B
B is also legal.
Then, for each
k
k
k, we only need to find
∑
i
=
1
k
A
i
\sum\limits_{i=1}^{k}A_i
The upper bound of i=1∑k?Ai? is sufficient. If a number occurs less than or equal to
k
k
k, it must be selected; if the number of occurrences is greater than
k
k
k, then at most
k
k
k times. set up
c
no
t
i
cnt_i
cnti? means
i
i
The number of occurrences of i, then
∑
i
=
1
k
A
i
≤
∑
i
=
1
k
min
?
(
k
,
c
no
t
i
)
\sum\limits_{i=1}^kA_i\leq \sum\limits_{i=1}^k\min(k,cnt_i)
i=1∑k?Ai?≤i=1∑k?min(k,cnti?). Next, the problem is transformed into a reset that satisfies the condition
A
A
The number of A’s.
We choose numbers from largest to smallest. set up
f
i
,
j
,
k
f_{i,j,k}
fi,j,k? indicates that the previous
i
i
i number, this
i
i
The sum of i numbers is
j
j
j, the smallest element in the resetable set is greater than or equal to
k
k
k. Then transfer as follows
f
i
,
j
,
k
=
f
i
,
j
,
k
+
1
+
[
j
≥
k
]
x
f
i
?
1
,
j
?
k
,
k
f_{i,j,k}=f_{i,j,k + 1} + [j \geq k]\times f_{i-1,j-k,k}
fi,j,k?=fi,j,k + 1? + [j≥k]×fi?1,j?k,k?
transferred to
o
(
1
)
O(1)
O(1), but the time complexity and space complexity are
o
(
no
3
)
O(n^3)
O(n3). We consider optimization.
For spaces, we can use rolling arrays to omit one dimension.
Let the current refocusable elements be
A
1
,
A
2
,
…
,
A
i
A_1,A_2,\dots,A_i
A1?,A2?,…,Ai?, obviously
A
1
,
A
2
,
…
,
A
i
≥
k
A_1,A_2,\dots,A_i\geq k
A1?,A2?,…,Ai?≥k, so
∑
j
=
1
i
A
j
≥
i
x
k
\sum\limits_{j=1}^iA_j\geq i\times k
j=1∑i?Aj?≥i×k. also because
∑
j
=
1
i
A
j
≤
no
\sum\limits_{j=1}^iA_j\leq n
j=1∑i?Aj?≤n, so
i
x
k
≥
no
i\times k\geq n
i×k≥n, that is
k
≤
no
i
k\leq \dfrac ni
k≤in?. That is, each enumeration
k
k
The time complexity of k is
o
(
no
i
)
O(\dfrac ni)
O(in?), then the total time complexity is
o
(
no
2
ln
?
no
)
O(n^2\ln n)
O(n2lnn).
code
#include <bits/stdc++.h>
using namespace std;
const int N=2000;
int n,x,cnt[2005],w[2005];
long long ans, f[2][2005][2005];
long long mod=998244353;
bool cmp(int ax,int bx){<!-- -->
return ax>bx;
}
int main()
{<!-- -->
scanf("%d", &n);
for(int i=1;i<=n;i + + ){<!-- -->
scanf("%d", &x); + + cnt[x];
}
sort(cnt + 1,cnt + n + 1,cmp);
for(int k=1;k<=n;k + + ){<!-- -->
for(int i=1;i<=n;i + + ) w[k] + =min(k,cnt[i]);
}
for(int i=0;i<=n;i + + ) f[0][0][i]=1;
for(int i=1,e=1;i<=n;i ++ ,e^=1){<!-- -->
for(int j=0;j<=w[i];j + + ){<!-- -->
f[e][j][n/i + 1]=0;
}
for(int k=n/i;k>=0;k--){<!-- -->
for(int j=0;j<=w[i];j + + ){<!-- -->
f[e][j][k]=f[e][j][k+1];
if(j>=k) f[e][j][k]=(f[e][j][k] + f[e^1][j-k][k])%mod;
}
}
}
printf("%lld",f[n &1][n][0]);
return 0;
}