天津区域赛题，首先可以观察到上升、下降位置的个数是一样的。假设有k对上升、下降的位置，那么这k对位置的合法组合数为Cat[k]。Cat为卡特兰数，这个组合问题等价于卡特兰数的经典应用括号化问题。设T[k]为n个位置中有k对上升、下降位置的组合数，这k对位置从n个位置中选出。所以T[k] = C(n,2*k)*Cat[k] = C(n,2*k)*C(2*k,k)/(k+1)。这样只需要枚举k即可，sum = T[0]+T[1]+...+T[m] (2*m<=n)。然而n<=10000，C(n,m)无法打表，也不好求。进一步可以推出T[k]/T[k-1] = (n-2*k+1)*(n-2*k+2)/(k*(k+1))。显然T[0] = 1，于是逐个递推出来即可。
import java.math.BigInteger;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);BigInteger mod = BigInteger.TEN.pow(100);BigInteger sum = new BigInteger("0");BigInteger t = new BigInteger("0");while (sc.hasNext()) {int n = sc.nextInt();sum = BigInteger.ONE;t = BigInteger.ONE;for(int k = 1; k + k <= n; k++) {t = t.multiply(BigInteger.valueOf((n-2*k+1)*(n-2*k+2))).divide(BigInteger.valueOf(k*(k+1)));sum = sum.add(t);}System.out.println(sum.mod(mod));}}
}