problem1 link
从前向后确定一下，然后再从后向前确定一下。一样的话就是可以确定的。
problem2 link
首先将强连通分量缩点。理论上来说，只需要遍历所有入度为0的联通块中的一个即可。
但是有一种情况可能是某个入度为0的联通块只包含一个节点$u$，这时当遍历完其他入度为0的联通块时即可确定节点$u$。
problem3 link
当$N$不能整除$H$时无解。
设连续的电梯长度为$L$。那么两个相邻的连续电梯块之间的长度也一定是$L$的倍数。
设$f(H,N)$表示$L>1$的答案，$g(H,N)$表示$L=1$的答案，那么题目的答案为$f(H,N)+g(H,N)$
其中$f(H,N)=\sum_{L|N,L>1}g(\frac{H}{L},\frac{N}{L})$
那么剩下的问题是如何计算$g(H,N)$。首先当$N=1$时，$g(H,N)=1$。
否则，设$N$节电梯当=的位置分别为$a_{0},a_{1},...,a_{N-1}$，其中$a_{0}=0$。电梯一共要停$\frac{H}{N}$次。设第$i$次停的时候最下面一节电梯所停的楼层为$b_{i}$。显然$b_{0}=0$
第一次停的楼层为 $a_{0}+b_{0},a_{1}+b_{0},...,a_{N-1}+b_{0}$
第二次停的楼层为 $a_{0}+b_{1},a_{1}+b_{1},...,a_{N-1}+b_{1}$
那么很显然$a_{0}+b_{1}=1$，因为$a_{1}+b_{0}=a_{1}\ne 1$
所以$b_{1}=1$
对于某一层楼$x$，一定存在唯一的二元组$(i,j)$满足$x=a_{i}+b_{j}$
交换数组$a,b$，可以看作现在是$\frac{H}{N}$节电梯，停$N$次。因此
$g(H,N)=\left\{\begin{matrix}1 & N=1\\ f(H,\frac{H}{N}) & N > 1\end{matrix}\right.$
code for problem1
public class ColorfulCards {
public int[] theCards(int N, String colors) {
boolean[] p = new boolean[N + 1];
for (int i = 1; i <= N; ++ i) {
p[i] = isprime(i);
}
final int x = colors.length();
int[] f = new int[x];
for (int id = 1, i = 0; i < x; ++ i) {
while (id <= N && !match(colors.charAt(i), p[id])) {
++ id;
}
if (id > N) {
f[i] = -1;
}
else {
f[i] = id ++;
}
}
for (int id = N, i = x - 1; i >= 0; -- i) {
while (id > 1 && !match(colors.charAt(i), p[id])) {
-- id;
}
if (id < 1) {
f[i] = -1;
}
else {
if (f[i] != id) {
f[i] = -1;
}
-- id;
}
}
return f;
}
static boolean match(char c, boolean b) {
return c == 'R' && b || c == 'B' && !b;
}
static boolean isprime(int x) {
if (x == 1) {
return false;
}
for (int i = 2; i * i <= x; ++ i) {
if (x % i == 0) {
return false;
}
}
return true;
}
}
code for problem2
import java.util.*;
import java.math.*;
import static java.lang.Math.*; public class CarrotBoxes { public double theProbability(String[] information) {
final int n = information.length;
boolean[][] g = new boolean[n][n];
for (int i = 0; i < n; ++ i) {
for (int j = 0; j < n; ++ j) {
g[i][j] = (information[i].charAt(j) == 'Y');
}
}
for (int i = 0; i < n; ++ i) {
for (int j = 0; j < n; ++ j) {
for (int k = 0; k < n; ++ k) {
if (g[j][i] && g[i][k]) {
g[j][k] = true;
}
}
}
}
List<Integer> top = new ArrayList<>();
boolean[] tag = new boolean[n];
for (int i = 0; i < n; ++ i) {
if (tag[i]) {
continue;
}
int ind = 0;
for (int j = 0; j < n; ++ j) {
if (g[j][i] && g[i][j]) {
tag[j] = true;
continue;
}
if (g[j][i]) {
++ ind;
break;
}
}
if (0 == ind) {
top.add(i);
}
}
final long all = (1l << n) - 1;
for (int i = 0; i < top.size(); ++ i) {
final int last = top.get(i);
long st = 0;
for (int j = 0; j < top.size(); ++ j) {
if (j == i) {
continue;
}
final int t = top.get(j);
for (int k = 0; k < n; ++ k) {
if (k != last && g[t][k]) {
st |= 1l << k;
}
}
}
if (st == (all ^ (1l << last))) {
return 1.0 * (n - (top.size() - 1)) / n;
}
}
return 1.0 * (n - top.size()) / n;
}
}
code for problem3
import java.util.*;
import java.math.*;
import static java.lang.Math.*; public class StrangeElevator {
final static long B = 1000000001;
final static int mod = 1000000007; Map<Long, Integer> Gmap = new HashMap<>();
Map<Long, Integer> Fmap = new HashMap<>(); public int theCount(int H, int N) {
if (H % N != 0) {
return 0;
}
return (F(H, N) + G(H, N)) % mod;
}
int G(int H, int N) {
if (N == 1) {
return 1;
}
if (Gmap.containsKey(H * B + N)) {
return Gmap.get(H * B + N);
}
int result = F(H, H / N);
Gmap.put(H * B + N, result);
return result;
} int F(int H, int N) {
if (Fmap.containsKey(H * B + N)) {
return Fmap.get(H * B + N);
}
int result = 0;
for (int i = 1; i * i <= N; ++ i) {
if (N % i == 0) {
if (i > 1) {
result += G(H / i, N / i);
result %= mod;
}
if (i *i != N) {
result += G(H / (N / i), i);
result %= mod;
}
}
}
Fmap.put(H * B + N, result);
return result;
}
}