p201.py
======================
import sys

sys.set_int_max_str_digits(100000)


class InputParser:
    def __init__(self):
        self.tokens = []
        self.index = 0

        # Read all input and split into tokens
        for line in sys.stdin:
            self.tokens.extend(line.strip().split())

    def next_int(self):
        """Read next integer from input."""
        result = int(self.tokens[self.index])
        self.index += 1
        return result

    def next_string(self):
        """Read next string from input."""
        result = self.tokens[self.index]
        self.index += 1
        return result

    def next_float(self):
        """Read next float from input."""
        result = float(self.tokens[self.index])
        self.index += 1
        return result


def main():
    # Problem: Count the number of strings of length N that are accepted by a DFA
    #          with non-absorbing edges.
    #
    # A DFA with non-absorbing edges has:
    # - Σ: input alphabet
    # - U: set of states
    # - s: initial state
    # - T: set of terminal states
    # - φ: transition function U × Σ → U
    # - χ: absorption function U × Σ → {0, 1}
    #
    # When χ(u, c) = 1, the character is not consumed (non-absorbing edge).
    # When χ(u, c) = 0, the character is consumed normally.
    #
    # Solution approach:
    # 1. Precompute effective transitions: For each (state, char), find the final state
    #    after following all non-absorbing transitions. This is to make the later DP easier.
    # 2. Use DP: dp[i][state] = number of ways to reach 'state' after consuming exactly i characters.
    #    We then simply try all other characters and figure out the state we reach using the
    #    precompute.
    #
    # The main reason we implement in Python is because in C++ we would need big integers.
    # Unfortunately, the original constraints are a bit too large for Python to pass, so we also implement
    # this in C++.

    # Read input alphabet
    alphabet = input().strip()
    alphabet_size = len(alphabet)

    parser = InputParser()
    k = parser.next_int()

    initial_state = parser.next_int() - 1
    num_terminal = parser.next_int()

    terminal_states = []
    for _ in range(num_terminal):
        terminal_states.append(parser.next_int() - 1)

    phi = [[0] * alphabet_size for _ in range(k)]
    for i in range(k):
        for j in range(alphabet_size):
            phi[i][j] = parser.next_int() - 1

    chi = [[0] * alphabet_size for _ in range(k)]
    for i in range(k):
        for j in range(alphabet_size):
            chi[i][j] = parser.next_int()

    n = parser.next_int()

    # Precompute effective transitions by resolving non-absorbing edges
    # trans[state][char] = final state after following all non-absorbing transitions
    trans = [[None] * alphabet_size for _ in range(k)]

    def dfs(state, char):
        """
        Resolve the chain of non-absorbing transitions starting from (state, char).
        Sets trans[state][char] to the final state where the character
        will actually be consumed. Sets to -1 if there's an infinite loop of
        non-absorbing edges.
        """
        if chi[state][char] == 0:
            # This is an absorbing edge, character gets consumed here
            trans[state][char] = state
            return

        if trans[state][char] is not None:
            return

        trans[state][char] = -1

        next_state = phi[state][char]
        dfs(next_state, char)
        trans[state][char] = trans[next_state][char]

    # Compute all effective transitions
    for state in range(k):
        for char in range(alphabet_size):
            if trans[state][char] is None:
                dfs(state, char)

    # Dynamic Programming
    # dp[i][state] = number of ways to be in 'state' after consuming
    #                exactly i characters
    dp = [[0] * k for _ in range(n + 1)]
    dp[0][initial_state] = 1

    # Fill DP table
    for length in range(n):
        for current_state in range(k):
            if dp[length][current_state] == 0:
                continue

            # Try each character in the alphabet
            for char in range(alphabet_size):
                absorbing_state = trans[current_state][char]
                assert absorbing_state is not None
                if absorbing_state == -1:
                    # Infinite loop of non-absorbing edges - skip
                    continue

                # Find where we end up after consuming this character
                # We follow non-absorbing edges to trans[current_state][char],
                # then consume the character and transition normally
                next_state = phi[absorbing_state][char]
                dp[length + 1][next_state] += dp[length][current_state]

    # Count strings that end in terminal states
    result = 0
    for terminal_state in terminal_states:
        result += dp[n][terminal_state]

    print(result)


if __name__ == "__main__":
    main()

=================
p201.ans1
======================
2

=================
p201.in1
======================
ab
2
1 1 2
2 1
1 2
0 1
0 0
3

=================
statement.txt
======================
201. Non Absorbing DFA
time limit per test: 0.25 sec.
memory limit per test: 65536 KB
input: standard
output: standard



In the theory of compilers and languages finite state machines, also known as finite automata are widely used. Deterministic finite automation (DFA) is an ordered set <Σ, U, s, T, φ> where Σ is the finite set called input alphabet, U is the finite set of states, s from U is the initial state, T subset of U is the set of terminal states and φ : U × Σ → U is the transition function.

The input of the automation is the string α over Σ. Initially the automation is in state s. Each step it reads the first character c of the input string and changes its state to φ(u, c) where u is the current state. After that the first character of the input string is removed and the step repeats. If when its input string is empty the automation is in the terminal state, it is said that it accepts the initial string α, in the other case it rejects it.

In some cases to simplify the automation the concept of nonabsorbing edges is introduced. That is, in addition to φ the function χ : U × Σ → {0, 1} is introduced and when making a transition from some state u with some character c, the leading character is removed from the input string only if χ(u, c) = 0. If χ(u, c) = 1, the input string is kept intact and next transition is performed with the new state and the same character.

It is said that such automation accepts some string α if after a number of steps it transits to the terminal state and the input string becomes empty.

Your task is given the DFA with nonabsorbing edges to compute the number of strings of the given length N that it accepts.

Input

The first line of the input file contains Σ — a subset of the English alphabet, several different small letters. Next line contains K = | U | — the number of states of the automation (1 ≤ K ≤ 1000). Let states be numbered from 1 to K. Next line contains S (1 ≤ S ≤ K) — the initial state, followed by L = | T | — the number of terminal states and then L different integer numbers ranging from 1 to K — the numbers of terminal states.

Next K lines contain | Σ | integer numbers each and define φ. Next K lines define χ in a similar way. The last line of the input file contains N (1 ≤ N ≤ 60).

Output

Output the only number — the number of different strings of length N over Σ that the given DFA accepts.

In the given example the two strings accepted by the automation are ``aaa'' and ``abb''.

Sample test(s)

Input
ab
2
1 1 2
2 1
1 2
0 1
0 0
3

Output
2

Author:	Andrew Stankevich
Resource:	Petrozavodsk Summer Trainings 2003
Date:	2003-08-23





=================
p201.cpp
======================
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

class BigInt {
  private:
    static const int BASE = (int)1e9;
    static const int BASE_LEN = 9;
    vector<int> digits;

  public:
    BigInt() : digits(1, 0) {}

    BigInt(int x) {
        if(x == 0) {
            digits = {0};
        } else {
            while(x > 0) {
                digits.push_back(x % BASE);
                x /= BASE;
            }
        }
    }

    BigInt& operator+=(const BigInt& other) {
        long long carry = 0;
        int max_size = max(digits.size(), other.digits.size());

        digits.resize(max_size);

        for(int i = 0; i < max_size || carry; i++) {
            if(i == digits.size()) {
                digits.push_back(0);
            }

            long long sum = digits[i] + carry;
            if(i < other.digits.size()) {
                sum += other.digits[i];
            }

            digits[i] = sum % BASE;
            carry = sum / BASE;
        }

        return *this;
    }

    BigInt operator+(const BigInt& other) const {
        BigInt result = *this;
        result += other;
        return result;
    }

    friend ostream& operator<<(ostream& out, const BigInt& x) {
        string result;
        for(int i = 0; i < (int)x.digits.size(); i++) {
            int val = x.digits[i];
            for(int j = 0; j < BASE_LEN; j++) {
                result.push_back('0' + val % 10);
                val /= 10;
            }
        }

        while(!result.empty() && result.back() == '0') {
            result.pop_back();
        }
        reverse(result.begin(), result.end());

        if(result.empty()) {
            result = "0";
        }
        out << result;
        return out;
    }
};

string alphabet;
int alphabet_size;
int k;
int initial_state;
vector<int> terminal_states;
vector<vector<int>> phi;
vector<vector<int>> chi;
int n;

void read() {
    cin >> alphabet;
    alphabet_size = alphabet.size();

    cin >> k;
    cin >> initial_state;
    initial_state--;

    int num_terminal;
    cin >> num_terminal;

    terminal_states.resize(num_terminal);
    for(int i = 0; i < num_terminal; i++) {
        cin >> terminal_states[i];
        terminal_states[i]--;
    }

    phi.assign(k, vector<int>(alphabet_size));
    for(int i = 0; i < k; i++) {
        for(int j = 0; j < alphabet_size; j++) {
            cin >> phi[i][j];
            phi[i][j]--;
        }
    }

    chi.assign(k, vector<int>(alphabet_size));
    for(int i = 0; i < k; i++) {
        for(int j = 0; j < alphabet_size; j++) {
            cin >> chi[i][j];
        }
    }

    cin >> n;
}

void solve() {
    /*
     * SGU Problem 201: Non Absorbing DFA
     *
     * Problem: Count the number of strings of length N that are accepted by a
     * DFA with non-absorbing edges.
     *
     * A DFA with non-absorbing edges has:
     * - Σ: input alphabet
     * - U: set of states
     * - s: initial state
     * - T: set of terminal states
     * - φ: transition function U × Σ → U
     * - χ: absorption function U × Σ → {0, 1}
     *
     * When χ(u, c) = 1, the character is not consumed (non-absorbing edge).
     * When χ(u, c) = 0, the character is consumed normally.
     *
     * Solution approach:
     * 1. Precompute effective transitions: For each (state, char), find the
     * final state after following all non-absorbing transitions.
     * 2. Use DP: dp[i][state] = number of ways to reach 'state' after consuming
     * exactly i characters.
     *
     * We use BigInt because the answer can be very large (up to
     * alphabet_size^N).
     */

    // Precompute effective transitions by resolving non-absorbing edges
    // trans[state][char] = final state after following all non-absorbing
    // transitions.
    vector<vector<int>> trans(k, vector<int>(alphabet_size, -2));

    function<void(int, int)> dfs = [&](int state, int ch) {
        if(chi[state][ch] == 0) {
            trans[state][ch] = state;
            return;
        }

        if(trans[state][ch] != -2) {
            return;
        }

        // Mark as being computed to detect cycles
        trans[state][ch] = -1;

        int next_state = phi[state][ch];
        dfs(next_state, ch);
        trans[state][ch] = trans[next_state][ch];
    };

    for(int state = 0; state < k; state++) {
        for(int ch = 0; ch < alphabet_size; ch++) {
            if(trans[state][ch] == -2) {
                dfs(state, ch);
            }
        }
    }

    // Dynamic Programming
    // dp[i][state] = number of ways to be in 'state' after consuming exactly i
    // characters.
    vector<vector<BigInt>> dp(n + 1, vector<BigInt>(k, BigInt(0)));
    dp[0][initial_state] = BigInt(1);

    for(int length = 0; length < n; length++) {
        for(int current_state = 0; current_state < k; current_state++) {
            for(int ch = 0; ch < alphabet_size; ch++) {
                if(trans[current_state][ch] == -1) {
                    // Infinite loop of non-absorbing edges - skip
                    continue;
                }

                int absorbing_state = trans[current_state][ch];
                int next_state = phi[absorbing_state][ch];
                dp[length + 1][next_state] += dp[length][current_state];
            }
        }
    }

    BigInt result(0);
    for(int terminal_state: terminal_states) {
        result += dp[n][terminal_state];
    }

    cout << result << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}

=================
