Complementary Teams (APCS 2019-06 Advanced Extended)

2.0s 256M

The \(m\) skills use A through Z, followed by a through l. Each team is represented by a nonempty string of skills; repeated letters count once. Two teams are complementary when their skill sets are disjoint and together contain every skill. Count unordered pairs of distinct teams. Identical sets may belong to different teams.

Input

Read \(m,n\), followed by \(n\) team strings.

Constraints

\(1\le m\le38\), \(1\le n\le500000\). Each string has \(1\) to \(1000\) characters, using only the first \(m\) skills.

Output

Print the number of complementary pairs.

Scoring

Each scored test independently awards 5 points, totaling 100. Samples award no points.

  • 1: 5% — \(m=2,n\le1000\); all sets are distinct.
  • 2: 20% — \(m\le26,n\le10000\); all sets are distinct.
  • 3: 50% — \(m\le26,n\le100000\); all sets are distinct.
  • 4: 25% — No additional restrictions; duplicate sets are allowed.

Sample Input

3 4
ABB
AB
C
CC

Sample Output

4

Source

e288 · 2019-06 APCS. Extended public version; the last 25% permits duplicate skill sets.

Problem page help

Keyboard shortcuts

Main features

  • Sample tests — Runs the sample cases bundled with the problem and auto-compares against the expected output.
  • Custom test — Run your code with your own stdin. Optionally tick the "Compare with expected (diff)" box to verify against expected output line-by-line.
  • Template — Paste the default code template you set on your profile page.
  • Collab — Edit this problem together with classmates in real time.
  • Auto-draft — Editor contents auto-save to your browser every 1.5 seconds (per account / problem / language).
  • Submit — Send your code to the judge for grading; returns AC / WA / TLE etc.

Limits

  • Source code: at most 65,536 characters
  • Custom test stdin and expected output: at most 1 MB each (≈1 million characters)
  • Custom test and sample test share the sandbox; about 1 request per 3 s per user (sample test: 1 per 1 s)
  • Custom test and sample test both have a 15 second wall-clock cap (the official judge still uses the problem time limit)
  • Interactive problems do not offer custom test (cannot simulate interaction with the judge).
  • Submitting has no rate limit, but rapid repeated submissions on the same problem are treated as score farming.