Conditional Mix (Codeforces 1740F)
Tags: Math, combinatorics

Pak Chanek is given an array $$$a$$$ of $$$n$$$ integers. For each $$$i$$$ ($$$1 \leq i \leq n$$$), Pak Chanek will write the one-element set $$$\{a_i\}$$$ on a whiteboard.After that, in one operation, Pak Chanek may do the following:   Choose two different sets $$$S$$$ and $$$T$$$ on the whiteboard such that $$$S \cap T = \varnothing$$$ ($$$S$$$ and $$$T$$$ do not have any common elements).  Erase $$$S$$$ and $$$T$$$ from the whiteboard and write $$$S \cup T$$$ (the union of $$$S$$$ and $$$T$$$) onto the whiteboard. After performing zero or more operations, Pak Chanek will construct a multiset $$$M$$$ containing the sizes of all sets written on the whiteboard. In other words, each element in $$$M$$$ corresponds to the size of a set after the operations.How many distinct$$$^\dagger$$$ multisets $$$M$$$ can be created by this process? Since the answer may be large, output it modulo $$$998\,244\,353$$$.$$$^\dagger$$$ Multisets $$$B$$$ and $$$C$$$ are different if and only if there exists a value $$$k$$$ such that the number of elements with value $$$k$$$ in $$$B$$$ is different than the number of elements with value $$$k$$$ in $$$C$$$.

Input: The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2000$$$).The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$).

Output: Output the number of distinct multisets $$$M$$$ modulo $$$998\,244\,353$$$.

Note: In the first example, the possible multisets $$$M$$$ are $$$\{1,1,1,1,1,1\}$$$, $$$\{1,1,1,1,2\}$$$, $$$\{1,1,1,3\}$$$, $$$\{1,1,2,2\}$$$, $$$\{1,1,4\}$$$, $$$\{1,2,3\}$$$, and $$$\{2,2,2\}$$$.As an example, let's consider a possible sequence of operations.   In the beginning, the sets are $$$\{1\}$$$, $$$\{1\}$$$, $$$\{2\}$$$, $$$\{1\}$$$, $$$\{4\}$$$, and $$$\{3\}$$$.  Do an operation on sets $$$\{1\}$$$ and $$$\{3\}$$$. Now, the sets are $$$\{1\}$$$, $$$\{1\}$$$, $$$\{2\}$$$, $$$\{4\}$$$, and $$$\{1,3\}$$$.  Do an operation on sets $$$\{2\}$$$ and $$$\{4\}$$$. Now, the sets are $$$\{1\}$$$, $$$\{1\}$$$, $$$\{1,3\}$$$, and $$$\{2,4\}$$$.  Do an operation on sets $$$\{1,3\}$$$ and $$$\{2,4\}$$$. Now, the sets are $$$\{1\}$$$, $$$\{1\}$$$, and $$$\{1,2,3,4\}$$$.  The multiset $$$M$$$ that is constructed is $$$\{1,1,4\}$$$. 

Sample Inputs:
6
1 1 2 1 4 3

7
3 5 4 3 7 4 5

Sample Outputs:
7

11

Solution (Python):
from sys import stdin, stdout
from collections import defaultdict
N = 998244353
n = int(stdin.readline())
a = [int(x) - 1 for x in stdin.readline().split()]
count = [0] * n
row_values = [0] * n
for i in range(n):
    row_values[count[a[i]]] += 1
    count[a[i]] += 1
row_values_pref = [row_values[0]]
for i in range(1, n):
    row_values_pref.append(row_values_pref[-1] + row_values[i])
dp = [[0] * (n + 1) for bar in range(n + 1)]
for i in range(1, row_values[0] + 1):
    dp[i][i] = 1
for i in range(1, n):
    for total in range(n - 1, 0, -1):
        current = 0
        for last in range(total // i, 0, -1):
            current += dp[total][last]
            current %= N
            dp[total][last] = 0
            if last <= min(row_values_pref[i] - total, n - total):
                dp[total + last][last] += current
                dp[total + last][last] %= N
answer = 0
for i in range(1, n + 1):
    answer += dp[n][i]
    answer %= N
stdout.write(str(answer) + '\n')

Solution (Python):
from __future__ import division, print_function
import os, sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip
from bisect import bisect_left as lower_bound, bisect_right as upper_bound

def so():
    return int(input())

def st():
    return input()

def mj():
    return map(int, input().strip().split(' '))

def msj():
    return map(str, input().strip().split(' '))

def le():
    return list(map(int, input().split()))

def rc():
    return map(float, input().split())

def lebe():
    return list(map(int, input()))

def dmain():
    sys.setrecursionlimit(1000000)
    threading.stack_size(1024000)
    thread = threading.Thread(target=main)
    thread.start()

def joro(L):
    return ''.join(map(str, L))

def joron(L):
    return '\n'.join(map(str, L))

def decimalToBinary(n):
    return bin(n).replace('0b', '')

def isprime(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

def npr(n, r):
    return factorial(n) // factorial(n - r) if n >= r else 0

def ncr(n, r):
    return factorial(n) // (factorial(r) * factorial(n - r)) if n >= r else 0

def lower_bound(li, num):
    answer = -1
    start = 0
    end = len(li) - 1
    while start <= end:
        middle = (end + start) // 2
        if li[middle] >= num:
            answer = middle
            end = middle - 1
        else:
            start = middle + 1
    return answer

def upper_bound(li, num):
    answer = -1
    start = 0
    end = len(li) - 1
    while start <= end:
        middle = (end + start) // 2
        if li[middle] <= num:
            answer = middle
            start = middle + 1
        else:
            end = middle - 1
    return answer

def tir(a, b, c):
    if 0 == c:
        return 1
    if len(a) <= b:
        return 0
    if c != -1:
        return tir(a, 1 + b, c + a[b]) or tir(a, b + 1, c - a[b]) or tir(a, 1 + b, c)
    else:
        return tir(a, 1 + b, a[b]) or tir(a, b + 1, -a[b]) or tir(a, 1 + b, -1)

def abs(x):
    return x if x >= 0 else -x

def binary_search(li, val, lb, ub):
    ans = -1
    while lb <= ub:
        mid = (lb + ub) // 2
        if li[mid] > val:
            ub = mid - 1
        elif val > li[mid]:
            lb = mid + 1
        else:
            ans = mid
            break
    return ans

def kadane(x):
    sum_so_far = 0
    current_sum = 0
    for i in x:
        current_sum += i
        if current_sum < 0:
            current_sum = 0
        else:
            sum_so_far = max(sum_so_far, current_sum)
    return sum_so_far

def pref(li):
    pref_sum = [0]
    for i in li:
        pref_sum.append(pref_sum[-1] + i)
    return pref_sum

def SieveOfEratosthenes(n):
    prime = [True for i in range(n + 1)]
    p = 2
    li = []
    while p * p <= n:
        if prime[p] == True:
            for i in range(p * p, n + 1, p):
                prime[i] = False
        p += 1
    for p in range(2, len(prime)):
        if prime[p]:
            li.append(p)
    return li

def primefactors(n):
    factors = []
    while n % 2 == 0:
        factors.append(2)
        n //= 2
    for i in range(3, int(sqrt(n)) + 1, 2):
        while n % i == 0:
            factors.append(i)
            n //= i
    if n > 2:
        factors.append(n)
    return factors

def read():
    sys.stdin = open('input.txt', 'r')
    sys.stdout = open('output.txt', 'w')

def tr(n):
    return n * (n + 1) // 2
boi = int(998244353)
doi = int(1000000000.0 + 7)
hoi = int(600000.0 + 5)
poi = int(2100)
y = 'YES'
n = 'NO'

def bulli(x):
    return bin(x).count('1')
import sys
d = []
for i in range(poi):
    Lo = []
    for j in range(poi):
        Lo.append(0)
    d.append(Lo)
L = [0] * poi
M = [0] * poi

def ty(a, b):
    rr = 1
    while b:
        if b % 2:
            rr = rr * a % boi
        b = b // 2
        a = a * a % boi
    return rr

def inv(a):
    return ty(a, boi - 2)

def ncr(m, k):
    if m < 0 or k < 0 or k > m:
        return 0
    return f[m] * r[k] % boi * r[m - k] % boi

def gosa(a, b):
    if 0 != b:
        return gosa(b, a % b)
    return a

def iu():
    import sys
    import math as my
    import functools
    import bisect as bs
    input = sys.stdin.readline
    from collections import deque, defaultdict
    ''
    m = so()
    P = le()
    bec = 0
    d[0][0] = 1
    for i in range(1, 1 + m):
        L[P[i - 1]] = 1 + L[P[i - 1]]
        M[L[P[i - 1]]] = 1 + M[L[P[i - 1]]]
    for i in range(1, 1 + m):
        M[i] = M[i - 1] + M[i]
    for i in range(m, 0, -1):
        j = 1
        while m >= i * j:
            for k in range(i * j, 1 + M[j]):
                d[j][k] = (d[j][k] + d[j - 1][k - i]) % boi
            j = 1 + j
    for i in range(1, 1 + m):
        bec = (bec + d[i][m]) % boi
    print(bec)

def main():
    for i in range(1):
        iu()
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
    """"""
    (sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop('end', '\n'))
    if kwargs.pop('flush', False):
        file.flush()
if sys.version_info[0] < 3:
    (sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
    (sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
if __name__ == '__main__':
    main()

Solution (Python):
import os, sys
from io import BytesIO, IOBase
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from heapq import heappush, heappop
from functools import lru_cache
from itertools import accumulate
import math
import sys
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
ii = lambda : int(input())
mii = lambda : map(int, input().split())
lmii = lambda : list(map(int, input().split()))
i2c = lambda n: chr(ord('a') + n)
c2i = lambda c: ord(c) - ord('a')
mod = 998244353

def solve():
    n = ii()
    l = lmii()
    N = 2050
    a = [0] * N
    for k in l:
        a[k] += 1
    sb = [0] * N
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            sb[i] += min(i, a[j])
    f = [[0] * N for _ in range(N)]
    f[0][0] = 1
    for t in range(n, 0, -1):
        for i in range(1, n // t + 1):
            for j in range(i * t, sb[i] + 1):
                f[i][j] = f[i][j] + f[i - 1][j - t]
                f[i][j] %= mod
    res = 0
    for i in range(1, n + 1):
        res += f[i][n]
        res %= mod
    print(res)
for _ in range(1):
    solve()