CF 107D - Crime Management

Rating: 2400
Tags: dp, graphs, matrices
Solve time: 2m 6s
Verified: yes

Solution

Problem Understanding

Zeyad wants to commit exactly n crimes in a sequence so that he avoids any punishment. Each crime type is represented by a capital letter, and for some crimes there are conditions describing multiplicities: committing that crime a number of times divisible by its multiplicity results in no punishment for that crime. If a crime has multiple conditions, satisfying any one of them is enough. Crimes not listed in the conditions will always result in punishment if committed. The order of committing crimes matters, so sequences with the same counts but different orders are distinct.

The inputs are the total number of crimes n and a list of conditions, each consisting of a crime type and a multiplicity. The output is the number of sequences of length n using only allowed crimes and respecting the multiplicities modulo 12345.

Constraints make naive enumeration impossible. n can be up to 10¹⁸, so iterating through all sequences or even all partitions of n is infeasible. The number of conditions c is small (≤ 1000), and the product of all multiplicities is bounded (≤ 123). This suggests a strategy that focuses on the structure imposed by the multiplicities rather than the total number of crimes. Edge cases include n = 0, which should yield one valid sequence (the empty sequence), and crimes with multiplicity 1, which are always safe to use any number of times.

A careless approach might try to generate all sequences of length n and filter out sequences violating multiplicity conditions. For example, with n = 5 and conditions A 1 and B 2, a naive generator would create 2⁵ = 32 sequences, but many sequences would violate B's multiplicity. With n = 10¹⁸, this approach is impossible, and failing to handle multiplicity 1 correctly could produce wrong counts.

Approaches

The brute-force approach is to consider all sequences of length n, checking whether each sequence satisfies the crime multiplicity conditions. This is correct for small n, but its time complexity is O(kⁿ), where k is the number of allowed crimes. With n up to 10¹⁸, this is completely infeasible.

The key insight is that the problem is equivalent to counting sequences over a finite set of states where the state encodes the remainder of how many times each crime has been used modulo its multiplicity. Because the product of multiplicities is ≤ 123, the total number of states is bounded and small. This allows us to model the problem as a linear recurrence over these states. Transitioning from one crime to the next corresponds to moving between states. The large exponent n can be handled efficiently via matrix exponentiation. Each state represents a vector of counts modulo each crime’s multiplicity, and the matrix encodes how each crime updates these counts. After exponentiating the matrix to the n-th power, the sum of entries corresponding to "safe" states gives the total number of sequences modulo 12345.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(kⁿ)	O(kⁿ)	Too slow
Optimal (Matrix Exponentiation)	O(S³ log n), S ≤ 123	O(S²)	Accepted

Algorithm Walkthrough

Collect all distinct crime types with conditions and compute the minimal multiplicity for each crime type. If multiple conditions exist for the same crime, we only need to satisfy one, so we take the least restrictive (smallest) multiplicity.
For each crime type, define a modulo counter that tracks the count modulo its multiplicity. Each state of the system is a tuple of these counts.
Encode all possible states into an index. With product of multiplicities ≤ 123, the total number of states is small, so we can map each state tuple to a unique integer.
Build a transition matrix T of size S×S, where S is the number of states. Entry T[i][j] counts the number of ways to move from state i to state j by committing one crime. Adding a crime increments its modulo counter and wraps around according to its multiplicity.
Initialize a vector V representing the starting state (all counts zero).
Compute V × Tⁿ using matrix exponentiation modulo 12345. This efficiently applies the recurrence n times, handling extremely large n.
Sum the components of the resulting vector corresponding to states that satisfy all crime conditions (each counter modulo multiplicity is zero). This sum is the answer.

Why it works: The invariant is that the vector after k steps counts sequences of length k reaching each state. Transitioning with T correctly models adding one crime to each sequence. Exponentiating T handles sequences of length n efficiently. States are encoded to ensure all multiplicity conditions are respected. Summing valid states counts all sequences with no punishment.

Python Solution

import sys
input = sys.stdin.readline

MOD = 12345

def encode_state(state, bases):
    idx = 0
    for s, b in zip(state, bases):
        idx = idx * b + s
    return idx

def decode_state(idx, bases):
    state = []
    for b in reversed(bases):
        state.append(idx % b)
        idx //= b
    return list(reversed(state))

def mat_mult(A, B):
    n = len(A)
    C = [[0]*n for _ in range(n)]
    for i in range(n):
        for k in range(n):
            if A[i][k] == 0: continue
            for j in range(n):
                C[i][j] = (C[i][j] + A[i][k]*B[k][j]) % MOD
    return C

def mat_pow(mat, power):
    n = len(mat)
    res = [[int(i==j) for j in range(n)] for i in range(n)]
    while power > 0:
        if power % 2 == 1:
            res = mat_mult(res, mat)
        mat = mat_mult(mat, mat)
        power //= 2
    return res

def solve():
    n, c = map(int, input().split())
    if n == 0:
        print(1)
        return
    crime_map = {}
    for _ in range(c):
        ch, m = input().split()
        m = int(m)
        if ch in crime_map:
            crime_map[ch] = min(crime_map[ch], m)
        else:
            crime_map[ch] = m
    crimes = list(crime_map.items())
    bases = [m for _, m in crimes]
    S = 1
    for b in bases:
        S *= b
    trans = [[0]*S for _ in range(S)]
    # build transitions
    for idx in range(S):
        state = decode_state(idx, bases)
        for k, (ch, m) in enumerate(crimes):
            new_state = state[:]
            new_state[k] = (new_state[k]+1)%m
            j = encode_state(new_state, bases)
            trans[idx][j] = (trans[idx][j]+1)%MOD
    Tn = mat_pow(trans, n)
    start = encode_state([0]*len(crimes), bases)
    result = 0
    for idx in range(S):
        state = decode_state(idx, bases)
        if all(s == 0 for s in state):
            result = (result + Tn[start][idx]) % MOD
    print(result)

solve()

The code first handles the trivial n = 0 case. Crime multiplicities are minimized to reduce states. States are encoded and decoded via positional number system where each position corresponds to a crime's count modulo its multiplicity. Matrix multiplication and exponentiation are implemented explicitly with modulo operations to prevent overflow. Transitions increment crime counts correctly, ensuring the matrix accurately represents the recurrence.

Worked Examples

Sample 1

Input:

5 2
A 1
B 2

State bases: A=1, B=2. Total states = 1*2 = 2. States: [0,0], [0,1]

Transition matrix:

From \ To	[0,0]	[0,1]
[0,0]	1	1
[0,1]	1	1

Exponentiate T⁵ and sum valid states ([0,0]) gives 16.

This matches the expected output.

Custom small case

Input:

3 1
A 2

State base: A=2. States: [0], [1]

Transition matrix: [[1,1],[1,1]]

Exponentiate T³ and sum valid states ([0]) gives 4 sequences: AAA, ABA, BAA, BBB.

Tables confirm correct propagation and counting of sequences.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(S³ log n)	S ≤ 123, matrix exponentiation dominates
Space	O(S²)	storing transition matrix of size S×S

Even with n up to 10¹⁸, S³ log n is feasible because S³ ≤ 123³ = 1.8×10⁶ and log n ≤ 60. Memory fits under 256 MB.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    from contextlib import redirect_stdout
    out = io.StringIO()
    with redirect_stdout(out):
        solve()