SGU 201 Non Absorbing DFA （DP）

自动机都给出了状态和转移，显然是个DP。。。

但是由于存在(u,c)=1的情况，即字符不变，所以需要预处理一下，得到最终接受字符的状态

记忆化搜索即可，可能出现死循环的情况，判定为不可转移

需要高精度

import java.util.*;
import java.io.*;
import java.math.*;
public class Solution {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		Task solver = new Task();
		solver.solve(in, out);
		out.close();
	}
}
class Task{
	static int go[][]=new int [1005][26];
	static boolean end[]=new boolean [1005];
	static int x[][]=new int [1005][26];
	static int to[][]=new int [1005][26];
	int dfs(int now,int ch){
		if(x[now][ch]==0){
			return to[now][ch]=go[now][ch];
		}
		if(to[now][ch]!=-1) 
			return to[now][ch];
		to[now][ch]=0;
		return to[now][ch]=dfs(go[now][ch],ch);
	}
	void solve(InputReader in,PrintWriter out){
		String S=in.next();
		int m=S.length();
		int n=in.nextInt();
		int s=in.nextInt();
		int endcnt=in.nextInt();
		for(int i=1;i<=n;i++)
			end[i]=false;
		for(int i=0;i0)
						dp[i][to[j][k]]=dp[i][to[j][k]].add(dp[i-1][j]);
				}
			}
		}
		BigInteger ans=BigInteger.ZERO;
		for(int i=1;i<=n;i++)
			if(end[i])
				ans=ans.add(dp[l][i]);
		out.println(ans);
	}
}
class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream));
        tokenizer = null;
    }

    public String next() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }
}