Problem Setting
다이아몬드 IV의견: 0
*Note: The memory limit for this problem is 512MB, twice the default.*
Farmer John created \(N\) (\(1\le N\le 10^5\)) problems. He then recruited \(M\)
(\(1\le M\le 20\)) test-solvers, each of which rated every problem as "easy" or
"hard."
His goal is now to create a problemset arranged in increasing order of
difficulty, consisting of some subset of his \(N\) problems arranged in some
order. There must exist no pair of problems such that some test-solver thinks
the problem later in the order is easy but the problem earlier in the order is
hard.
Count the number of distinct nonempty problemsets he can form, modulo \(10^9+7\).
Problem credits: Benjamin Qi
SCORING
- Inputs 3-4: \(M=1\)
- Inputs 5-14: \(M\le 16\)
- Inputs 15-22: No additional constraints.
Problem credits: Benjamin Qi
The first line contains \(N\) and \(M\).
The next \(M\) lines each contain a string of length \(N\). The \(i\)th character of
this string is E if the test-solver thinks the \(i\)th problem is easy, or H
otherwise.
The number of distinct problemsets FJ can form, modulo \(10^9+7\).
3 1
EHE9The nine possible problemsets are as follows:
[1]
[1,2]
[1,3]
[1,3,2]
[2]
[3]
[3,1]
[3,2]
[3,1,2]
Note that the order of the problems within the problemset matters.
10 6
EHEEEHHEEH
EHHHEEHHHE
EHEHEHEEHH
HEHEEEHEEE
HHEEHEEEHE
EHHEEEEEHE33riseoj 작성
출처 올림피아드 > USACO > 2022-2023 > February > Platinum
평가 및 의견
Problem Setting
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Problem Setting