topcoder srm 490 div1

problem1

首先每$n*m$一定是一个循环，所以只需要考虑时间$[0,n*m-1]$即可。这个期间一共出现了$n$个，第i个的出现时间为$m*i$，离开的时间为$\left \lceil \frac{mi}{n} \right \rceil*n$，所有答案为:

ans=$\frac{\sum_{i=0}^{n-1}(\left \lceil \frac{mi}{n} \right \rceil*n-mi)}{n}$

=$\frac{n\sum_{i=0}^{n-1}\left \lceil \frac{mi}{n} \right \rceil-\sum_{i=0}^{n-1}mi}{n}$

=$\sum_{i=0}^{n-1}\left \lceil \frac{mi}{n} \right \rceil-\frac{(n-1)m}{2}$

设$A=\sum_{i=0}^{n-1}\left \lceil \frac{mi}{n} \right \rceil=\sum_{i=0}^{n-1}\left \lfloor \frac{mi}{n} \right \rfloor+n-X$ 

其中$X$是那些$mi$正好是$n$的倍数因此不需要加1的个数。

现在的问题是计算$B=\sum_{i=0}^{n-1}\left \lfloor \frac{mi}{n} \right \rfloor$

它等于$\sum_{i=0}^{n-1}\left \lfloor \frac{mi}{n} \right \rfloor=\frac{(n-1)(m-1)}{2}-\frac{gcd(n,m)-1}{2}$

这个的证明在具体数学中文版第二版第77页到第78页。

problem2

首先将所有的前缀编号，预处理转换表$T[id][k]$表示前缀id在输入$k$时转换到的状态，其中$k$表示数字以及星号。

然后设$f[i][id]$表示当前“fix”部分为$word$的前$i$个，且"unfix"部分的标号为id的最小操作次数。然后进行dp即可。

problem3

首先，在$n*m$个一个pattern中(n为高度，m为宽度)，位置$(x_{1},y_{1})$到位置$(x_{2},y_{2})$的最短路径可能会经过其他重复的pattern。可以证明，如果经过该patern上面的pattern，最多只需要考虑$\left \lceil \frac{m}{2} \right \rceil^{2}$个

假设每次进入上面一个pattern是进入是第$i$列，出来时是第$j$列，$i \ne j$。那么不会出现两个pattern进入出来时的$i,j$一模一样，否则可以省略中间的一些pattern。这样考虑的话不同的$i,j$对有$\frac{m(m-1)}{2}$个，所以至多向上考虑这么多即可。

进一步考虑。将pattern的最后一行按照连续的空列分成若干组，那么很明显最多有$\left \lceil \frac{m}{2} \right \rceil$组（每隔一个空列有一个障碍格子）。跟上面同样的考虑方法，进入的组和出来的组不会有两个pattern是完全一样的，否则可以省略（因为一个组是联通的）。所以向上最多需要考虑$\left \lceil \frac{m}{2} \right \rceil^{2}$个pattern即可。

这样就可以处理出一个$m*m$的矩阵$A[i][j]$，表示从pattern的第一行的第 $i$ 列格子到达下一个pattern的第一行的第$j$列格子的最短路径。

这样的话，对于那么$r_{1},r_{2}$中间有很多pattern的情况，可以进行类似矩阵幂的优化。

code for problem1

import java.util.*;
import java.math.*;
import static java.lang.Math.*;

public class Starport {

	public double getExpectedTime(int N, int M) {
		long t = (long)(N - 1) * M;
		long r = upper(N, M) - t / 2;
		if (t % 2 == 0) {
			return r;
		}
		return r - 0.5;
	}

	long upper(long n, long d) {
		if (n == 1) {
			return 0;
		}
		long nn = n / gcd(n, d);
		long p = (n - 1) / nn + 1;
		return lower(n, d) + n - p;
	}

	long gcd(long x, long y) {
		if (y == 0) {
			return x;
		}
		return gcd(y, x % y);
	}

	long lower(long n, long m) {
		return ((n - 1) * (m - 1) + gcd(n, m) - 1) / 2;
	}

}

code for problem2

import java.util.*;
import java.math.*;
import static java.lang.Math.*;

public class QuickT9 {

	static int[] D = new int[]{3, 3, 3, 3, 3, 4, 3, 4};

	int prefixIndex = 0;
	Map map = new HashMap<>();    //串对应编号
	Map mapRev = new HashMap<>(); //编号对应串
	Map> mapForNext = new HashMap<>();  //数字串对应的串
	Map mapToDigit = new HashMap<>();        //串对应的数字串
	List allWords = new ArrayList<>();

	String word;

	int[][] g = null;
	int[][] f = null;

	public int minimumPressings(String[] t9, String word) {
		init(t9);
		this.word = word;
		final int n = word.length();
		f = new int[n + 1][prefixIndex];
		for (int i = 0; i <= n; ++ i) {
			Arrays.fill(f[i], -1);
		}
		f[0][0] = 0;
		for (int i = 0; i < n; ++ i) {
			bfs(i);
		}
		return f[n][0];
	}

	Queue queue = new LinkedList<>();
	boolean[] inq = null;

	void bfs(int len) {
		if (inq == null) {
			inq = new boolean[prefixIndex + 1];
		}

		if (f[len][0] != -1) {
			queue.offer(0);
		}
		while (!queue.isEmpty()) {
			int st = queue.poll();
			inq[st] = false;
			for (int i = 0; i < 11; ++ i) {
				if (i < 9) {
					int nxt = g[st][i];
					int c = f[len][st] + 1;
					if (f[len][nxt] == -1 || f[len][nxt] > c) {
						f[len][nxt] = c;
						if (!inq[nxt]) {
							queue.offer(nxt);
							inq[nxt] = true;
						}
					}
				}
				else {
					int[] result = check(st, len, i == 10);
					int t = result[0];
					int c = result[1];
					if (t > 0) {
						if (f[len + t][0] == -1 || f[len + t][0] > f[len][st] + 1 + c) {
							f[len + t][0] = f[len][st] + 1 + c;
						}
					}
				}
			}
		}
	}

	void init(String[] all) {
		for (int i = 0; i < all.length; ++ i) {
			String[] t= all[i].split("\\W+");
			for (String p : t) {
				String x = p.trim();
				if (x.length() > 0) {
					allWords.add(x);
				}
			}
		}
		addPrefix("", "");
		for (int i = 0; i < allWords.size(); ++ i) {
			String originStr = "";
			String digitStr = "";
			String s = allWords.get(i);
			for (int j = 0; j < s.length(); ++ j) {
				digitStr += getDigit(s.charAt(j));
				originStr += s.charAt(j);
				addPrefix(originStr, digitStr);
			}
		}

		for (String s: mapForNext.keySet()) {
			Collections.sort(mapForNext.get(s));
		}
		g = new int[prefixIndex][9];
		for (int i = 0; i < prefixIndex; ++ i) {
			for (int j = 0; j < 9; ++ j) {
				if (j == 0) {
					g[i][j] = getNext(i);
				}
				else {
					g[i][j] = getAddDigit(i, j + 1);
				}

			}
		}
	}

	int[] check(int id, int preIndex, boolean isStar) {
		if (id == 0) {
			return new int[]{0,0};
		}
		String s = mapRev.get(id);
		String sub = word.substring(preIndex);
		if (isStar) {
			s = s.substring(0, s.length() - 1);
		}
		int comPre = 0;
		for (int i = 0; i < sub.length() && i < s.length(); ++ i) {
			if (sub.charAt(i) == s.charAt(i)) {
				++comPre;
			}
			else {
				break;
			}
		}
		return new int[]{comPre, s.length() - comPre};
	}


	int getNext(int id) {
		if (id == 0) {
			return 0;
		}
		String s = mapRev.get(id);
		String digitStr = mapToDigit.get(s);
		List list = mapForNext.get(digitStr);
		int index = list.indexOf(s);
		String nextOriginStr = list.get((index + 1) % list.size());
		return map.get(nextOriginStr);
	}
	int getAddDigit(int id, int d) {
		String s = mapRev.get(id);
		String digitStr0 = mapToDigit.get(s);
		String digitStr1 = digitStr0 + (char)(‘0‘ + d);
		if (!mapForNext.containsKey(digitStr1)) {
			return id;
		}
		List list = mapForNext.get(digitStr1);
		return map.get(list.get(0));
	}

	void addPrefix(String originStr, String digitStr) {
		if (!map.containsKey(originStr)) {
			map.put(originStr, prefixIndex);
			mapRev.put(prefixIndex, originStr);
			++ prefixIndex;
		}
		if (!mapForNext.containsKey(digitStr)) {
			mapForNext.put(digitStr, new ArrayList<>());
		}
		if (!mapForNext.get(digitStr).contains(originStr)) {
			mapForNext.get(digitStr).add(originStr);
		}
		mapToDigit.put(originStr, digitStr);
	}

	static char getDigit(char c) {
		int t = c - ‘a‘ + 1;
		for (int i = 0; i < D.length; ++ i) {
			if (t > D[i]) {
				t -= D[i];
			}
			else {
				return (char)(‘2‘ + i);
			}
		}
		return 0;
	}
}

code for problem3

import java.util.*;


public class InfiniteLab {

	final static int[] dx = {0, 0, 1, -1};
	final static int[] dy = {1, -1, 0, 0};
	final static int MAX_EXTENDED = 100;

	int n, m;
	String[] map;
	int[][] T;
	int[][][][] d;

	public long getDistance(String[] map, long r1, int c1, long r2, int c2) {
		if (r1 > r2) {
			return getDistance(map, r2, c2, r1, c1);
		}
		if (r1 < 0 || r1 >= map.length) {
			long det = r2 - r1;
			long b = (Math.abs(r1) / map.length + 1) * map.length;
			r1 = (r1 + b) % map.length;
			return getDistance(map, r1, c1 , r1 + det, c2);
		}

		this.map = map;
		n = map.length;
		m = map[0].length();
		T = new int[n][2];
		for (int i = 0; i < n; ++ i) {
			T[i][0] = T[i][1] = -1;
			for (int j = 0; j < m; ++ j) {
				if (map[i].charAt(j) == ‘T‘) {
					if (T[i][0] == -1) {
						T[i][0] = j;
					}
					else {
						T[i][1] = j;
					}
				}
			}
		}
		d = new int[m][n][m][n + 1];
		cal();

		if (r2 <= n) {
			int t = d[c1][(int)r1][c2][(int)r2];
			if (t == Integer.MAX_VALUE) {
				t = -1;
			}
			return t;
		}
		long[][] a = new long[m][m];
		long[][] b = new long[m][m];
		for (int i = 0; i < m; ++ i) {
			for (int j = 0; j < m; ++ j) {
				a[i][j] = -1;
				if (d[i][0][j][n] != Integer.MAX_VALUE) {
					a[i][j] = d[i][0][j][n];
				}
				if (i == j) {
					b[i][j] = 0;
				}
				else {
					b[i][j] = -1;
				}
			}
		}
		long p = r2 / n - r1 / n - 1;
		while (p > 0) {
			if ((p & 1) == 1) {
				b = multipy(b, a);
			}
			a = multipy(a, a);
			p >>= 1;
		}
		long result = -1;
		for (int i = 0; i < m; ++ i) {
			for (int j = 0; j < m; ++ j) {
				if (d[c1][(int)r1][i][n] != Integer.MAX_VALUE
						&& b[i][j] != -1
						&& d[j][0][c2][(int)(r2 % n)] != Integer.MAX_VALUE) {
					long w = d[c1][(int)r1][i][n] + b[i][j] + d[j][0][c2][(int)(r2 % n)];
					if (result == -1 || result > w) {
						result = w;
					}
				}
			}
		}
		return result;
	}

	long[][] multipy(long[][] A, long[][] B) {
		long[][] result = new long[m][m];
		for (int i = 0; i < m; ++ i) {
			for (int j = 0; j < m; ++ j) {
				result[i][j] = -1;
				for (int k = 0; k < m; ++ k) {
					if (A[i][k] != -1 && B[k][j] != -1) {
						long t = A[i][k] + B[k][j];
						if (result[i][j] == -1 || result[i][j] > t) {
							result[i][j] = t;
						}
					}
				}
			}
		}
		return result;
	}

	int trans(int x, int y) {
		x %= n;
		if (map[x].charAt(y) == ‘T‘) {
			return T[x][0] + T[x][1] - y;
		}
		return -1;
	}
	boolean empty(int x, int y) {
		return map[x % n].charAt(y) != ‘#‘;
	}
	void cal() {
		final int N = (2 * MAX_EXTENDED + 1) * n;
		int[][] f = new int[N][m];
		Queue queue = new LinkedList<>();
		for (int sx = 0; sx < n; ++ sx) {
			for (int sy = 0; sy < m ; ++ sy) {
				final int startX =sx + MAX_EXTENDED * n;
				final int startY = sy;
				while (!queue.isEmpty()) {
					queue.poll();
				}
				for (int i = 0; i < N; ++ i) {
					Arrays.fill(f[i], Integer.MAX_VALUE);
				}
				f[startX][startY] = 0;
				queue.offer(startX * 100 + startY);
				while (!queue.isEmpty()) {
					int x = queue.peek() / 100;
					int y = queue.poll() % 100;
					int nxtCost = f[x][y] + 1;

					for (int i = 0; i < 4; ++ i) {
						int xx = x + dx[i];
						int yy = y + dy[i];
						if (xx >= 0 && xx < N && yy >= 0 && yy < m && empty(xx, yy) && f[xx][yy] > nxtCost) {
							f[xx][yy] = nxtCost;
							queue.offer(xx * 100 + yy);
						}
					}
					if (trans(x, y) != -1) {
						int y1 = trans(x, y);
						if (f[x][y1] > nxtCost) {
							f[x][y1] = nxtCost;
							queue.offer(x * 100 + y1);
						}
					}
				}
				for (int i = 0; i <= n; ++ i) {
					for (int j = 0; j < m; ++ j) {
						d[sy][sx][j][i] = f[i + MAX_EXTENDED * n][j];
					}
				}
			}
		}
	}

}