题解 | #钉子和小球#

萌新蒻够第一次写题解呜呜

先把整个无论是钉子还空格都视为能到达的位置用二维数组存储能到达的概率分子，n不太大空间问题不大。

如果n层则最后概率分母可以表示为2^n,gailv = (long) Math.pow(2, n);只需要把这个初始化后最上面向下分就行。

	d = n * 2 + 1;
	zx = d / 2 + 1; 
	dp[0][zx] = gailv;

状态转移在每一层

dp[i][p] = dps(i - 1, p, 0) + dps(i - 1, p - 1, -1) + dps(i - 1, p + 1, 1);

从上方，左边，右边过来的

static long dps(int h, int l, int kind) {
	if (kind == 0) {//上方过来的
		if (a[h][l] != 1)
			return dp[h][l];//上方没钉子
		else {
			return 0;//上方有钉子
		}
	} else {
		if (a[h][l] == 1)//左上右上过来的有钉子
			return dp[h][l] / 2;//概率分母向下分
		else {
			return 0;//左上右上没钉子
		}
	}
}

最后dp[n + 1][zcx]就是结果的分子

while (dp[n + 1][zcx] % 2 == 0 && gailv % 2 == 0) {
		dp[n + 1][zcx] /= 2;//分母是2^n一直判断2就行了
		gailv /= 2;
	}
	printf("%d/%d", dp[n + 1][zcx], gailv);
    
    
    

完整代码

import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {
static int n, cx, d, a[][], zx, zcx;
static long dp[][], gailv;

static long dps(int h, int l, int kind) {
	if (kind == 0) {
		if (a[h][l] != 1)
			return dp[h][l];
		else {
			return 0;
		}
	} else {
		if (a[h][l] == 1)
			return dp[h][l] / 2;
		else {
			return 0;
		}
	}
}

public static void main(String[] args) throws NumberFormatException, IOException {
	// TODO Auto-generated method stub
	n = nextint();
	cx = nextint();
	zcx = cx * 2 + 1;
	d = n * 2 + 1;
	zx = d / 2 + 1;
	gailv = (long) Math.pow(2, n);
	a = new int[d + 1][d + 1];
	dp = new long[d + 1][d + 1];

	dp[0][zx] = gailv;
	for (int i = 1; i <= n; i++) {
		int qd = zx - i + 1;
		for (int p = 1; p <= i; p++) {
			char x = next().charAt(0);
			if (x == '*') {
				a[i][qd + 2 * (p - 1)] = 1;
			}
		}
	}
	for (int i = 1; i <= n + 1; i++) {
		for (int p = 1; p < d; p++) {
			dp[i][p] = dps(i - 1, p, 0) + dps(i - 1, p - 1, -1) + dps(i - 1, p + 1, 1);
		}
	}
	while (dp[n + 1][zcx] % 2 == 0 && gailv % 2 == 0) {
		dp[n + 1][zcx] /= 2;
		gailv /= 2;
	}
	printf("%d/%d", dp[n + 1][zcx], gailv);
	flsh();
}

static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static PrintWriter pw = new PrintWriter(new BufferedOutputStream(System.out));

static String next() throws IOException {
	while (st == null || !st.hasMoreElements()) {

		String lineString = br.readLine();
		st = new StringTokenizer(lineString);
	}
	return st.nextToken();
}

static boolean hasnext() throws IOException {
	if (st != null && st.hasMoreElements()) {
		return false;
	}
	br.mark(1024);
	String s = br.readLine();
	br.reset();
	return s != null && !s.isEmpty();
}

static int nextint() throws NumberFormatException, IOException {
	return Integer.parseInt(next());
}

static long nextlong() throws NumberFormatException, IOException {
	return Long.parseLong(next());
}

static double nextdouble() throws NumberFormatException, IOException {
	return Double.parseDouble(next());
}

static String nextline() throws IOException {
	return br.readLine();// ??
}

static void println(Object o) {
	pw.println(o);
}

static void println() {
	pw.println();
}

static void printf(String s, Object... o) {
	pw.printf(s, o);
}

static void flsh() {
	pw.flush();
}
}