ASC(2)A(大数+図論DP)
Non Absorbing DFA
Time Limit: 10000/5000MS (Java/Others)
Memory Limit: 128000/64000KB (Java/Others)
Submit Statistic Next Problem
Problem Description
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 ∈U is the initial state, T ⊂ 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.
Sample Input
Sample Output
Hint
In the given example the two strings accepted by the automation are “aaa” and “abb”.
标题:気持ち悪くて、いっぱい言いたいのか言わないのか==という感じで、その時もこの問題は見て泣いていました
構想:自動機を有向図と見なし、状態を点と見なし、アルファベットをエッジと見なし、
まずX[u][c]関数に基づいて図を前処理し,X[u][c]=1であればこの辺に沿って広がり,リングを形成すればこの歩き方は絶対にできない.
そうでなければ、この状態の次のステップを最も早く歩ける状態として直接マークする(X[u 1][c 1]=0)
詳細はコードを見てください.再帰と再帰の2つのバージョンが書かれています.再帰はもっと速いです.
Time Limit: 10000/5000MS (Java/Others)
Memory Limit: 128000/64000KB (Java/Others)
Submit Statistic Next Problem
Problem Description
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 ∈U is the initial state, T ⊂ 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.
Sample Input
ab
2
1 1 2
2 1
1 2
0 1
0 0
3Sample Output
2Hint
In the given example the two strings accepted by the automation are “aaa” and “abb”.
标题:気持ち悪くて、いっぱい言いたいのか言わないのか==という感じで、その時もこの問題は見て泣いていました
構想:自動機を有向図と見なし、状態を点と見なし、アルファベットをエッジと見なし、
まずX[u][c]関数に基づいて図を前処理し,X[u][c]=1であればこの辺に沿って広がり,リングを形成すればこの歩き方は絶対にできない.
そうでなければ、この状態の次のステップを最も早く歩ける状態として直接マークする(X[u 1][c 1]=0)
詳細はコードを見てください.再帰と再帰の2つのバージョンが書かれています.再帰はもっと速いです.