### Andrew Stankevich’s Contest #2解题报告 » ZOJ2337

ZOJ2337.java

```import java.math.*;
import java.util.*;

class DFA {
private int z, k, s;
private int[] t;
private int[][] e;

private int dfs(int p, int[] e, int[] f, boolean[] g) {
if (e[p] == -1) {
} else if (g[p]) {
e[p] = f[p];
} else {
e[p] = -1;
e[p] = dfs(f[p], e, f, g);
}
return e[p];
}

public DFA(char[] z, int k, int s, int[] t, int[][] f, boolean[][] g) {
this.z = z.length;
this.k = k;
this.s = s;
this.t = t.clone();
e = new int[z.length][k];
for (int i = 0; i < z.length; ++i) {
Arrays.fill(e[i], -2);
for (int j = 0; j < k; ++j) {
if (e[i][j] == -2) {
dfs(j, e[i], f[i], g[i]);
}
}
}
}

public BigInteger count(int n) {
BigInteger[] prev = new BigInteger[k];
Arrays.fill(prev, BigInteger.ZERO);
prev[s] = BigInteger.ONE;
while (n-- > 0) {
BigInteger[] next = new BigInteger[k];
Arrays.fill(next, BigInteger.ZERO);
for (int i = 0; i < k; ++i) {
if (prev[i].signum() <= 0) {
continue;
}
for (int j = 0; j < z; ++j) {
if (e[j][i] < 0) {
continue;
}
}
}
prev = next;
}
BigInteger ans = BigInteger.ZERO;
for (int term : t) {
}
return ans;
}
}

public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int re = in.nextInt();
for (int ri = 1; ri <= re; ++ri) {
if (ri > 1) {
System.out.println();
}
String z = in.next();
int k = in.nextInt();
int s = in.nextInt() - 1;
int l = in.nextInt();
int[] t = new int[l];
for (int i = 0; i < l; ++i) {
t[i] = in.nextInt() - 1;
}
int[][] f = new int[z.length()][k];
for (int i = 0; i < k; ++i) {
for (int j = 0; j < z.length(); ++j) {
f[j][i] = in.nextInt() - 1;
}
}
boolean[][] g = new boolean[z.length()][k];
for (int i = 0; i < k; ++i) {
for (int j = 0; j < z.length(); ++j) {
g[j][i] = (in.nextInt() == 0);
}
}
DFA dfa = new DFA(z.toCharArray(), k, s, t, f, g);
int n = in.nextInt();
System.out.println(dfa.count(n));
}
}
}
//Run ID  	Submit Time  	Judge Status  	Problem ID  	Language  	Run Time(ms)  	Run Memory(KB)  	User Name
//1784603 	2009-03-10 22:56:24 	Accepted 	2337 	Java 	0 	4434 	watashi@Zodiac
```
3 Responses to “ZOJ2337”
1. zzzz says:

求路径种数，如果数据大小允许的话可以用矩阵乘法来做吗？

• watashi says:

如果长度N很大，但是点数V不太大的时候，就选择O(V^3lg N)的矩阵乘法；如果N不是很大，V也不小的时候，就选择O(NV)的直接DP。应该是这样吧。

• zzzz says:

Gotta Thank you!

2.