problem1 link
首先每$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 link
首先将所有的前缀编号，预处理转换表$T[id][k]$表示前缀id在输入$k$时转换到的状态，其中$k$表示数字以及星号。
然后设$f[i][id]$表示当前“fix”部分为$word$的前$i$个，且"unfix"部分的标号为id的最小操作次数。然后进行dp即可。
problem3 link
首先，在$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<String, Integer> map = new HashMap<>(); //串对应编号
Map<Integer, String> mapRev = new HashMap<>(); //编号对应串
Map<String, List<String>> mapForNext = new HashMap<>(); //数字串对应的串
Map<String, String> mapToDigit = new HashMap<>(); //串对应的数字串
List<String> 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<Integer> 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<String> 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<String> 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<Integer> 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];
}
}
}
}
}
}