"买到同类票"的概率（洛谷P2719题题解，Java语言描述）

题目要求

P2719题目链接

分析

没有选择动归实现，排列组合就可以啦！

事先说明： C 2 n − 2 n − 1 < = > ( 2 n − 2 n − 1 ) C_{2n-2}^{n-1} \binom{2n-2}{n-1} C2n−2n−1​(n−12n−2​)

最后两张票属于不同类的概率： ( 2 n − 2 n − 1 ) × ( 1 2 ) 2 n − 2 \binom{2n-2}{n-1} \times (\frac{1}{2})^{2n-2} (n−12n−2​)×(21​)2n−2 ∴ \therefore ∴ 此时，前 ( 2 n − 2 ) (2n-2) (2n−2) 张里有 ( n − 1 ) (n-1) (n−1) 张A， ( n − 1 ) (n-1) (n−1) 张B

( 2 n − 2 n − 1 ) × ( 1 2 ) 2 n − 2 = ( 2 n − 2 ) ! 4 n − 1 ( n − 1 ) ! ( n − 1 ) ! = ( 2 n − 2 ) ( 2 n − 3 ) ⋯ ( n ) [ 4 ( n − 1 ) ] [ 4 ( n − 2 ) ] ⋯ [ 4 × 1 ] \binom{2n-2}{n-1} \times (\frac{1}{2})^{2n-2} = \frac{(2n-2)!}{4^{n-1}(n-1)!(n-1)!} = \frac{(2n-2)(2n-3)\cdots(n)}{[4(n-1)][4(n-2)]\cdots[4\times1]} (n−12n−2​)×(21​)2n−2=4n−1(n−1)!(n−1)!(2n−2)!​=[4(n−1)][4(n−2)]⋯[4×1](2n−2)(2n−3)⋯(n)​

迭代运算即可得到答案！

补一发DP的动态转移方程： f [ i ] [ j ] = ( f [ i − 1 ] [ j ] + f [ i ] [ j − 1 ] ) 2 f[i][j]=\frac{(f[i-1][j]+f[i][j-1])}{2} f[i][j]=2(f[i−1][j]+f[i][j−1])​

AC代码（Java语言描述）

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt()>>1;
        scanner.close();
        double result = 1.0;
        for (int i = 1; i