problem1

从前向后确定一下，然后再从后向前确定一下。一样的话就是可以确定的。

problem2

首先将强连通分量缩点。理论上来说，只需要遍历所有入度为0的联通块中的一个即可。

但是有一种情况可能是某个入度为0的联通块只包含一个节点$u$，这时当遍历完其他入度为0的联通块时即可确定节点$u$。

problem3

当$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
     
       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
     
       Gmap = new HashMap<>();	Map
      
        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;	}}