您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

ZOJ 3380 Patchouli's Spell Cards - 概率 DP 計算元素相位匹配

編輯：C++ 入門

題目大意

m 種元素，每種有 n 種相位（等概率）。
隨機為每種元素選一相位。相同相位的元素可融合，融合數 = 法術等級。
求等級 ≥ l 的概率，輸出既約分數。
m, n, l ≤ 100。

解法：DP 計算互補事件

狀態定義

dp[i][j]：前 i 個相位，已使用 j 個元素，且最大融合數 < l 的方案數。
用大整數 (BigInteger) 避免溢位。

轉移

第 i 個相位選 k 個元素 (0 ≤ k < l)：

dp[i][j] = Σ_{k=0}^{min(j, l-1)} dp[i-1][j-k] × C(m - (j-k), k)

C(a, b)：從剩餘 a 元素中選 k 個賦予此相位。

初始與答案

dp[0][0] = 1
總方案數 = n^m
合法方案 = dp[n][m]
答案 = (n^m - dp[n][m]) / n^m 約分

Java 大整數實作

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    static final int MAX = 110;
    static BigInteger[][] dp = new BigInteger[MAX][MAX];
    static BigInteger[][] C = new BigInteger[MAX][MAX];
    
    public static void main(String[] args) {
        // 預計算組合數
        for (int i = 0; i < MAX; i++) {
            C[i][0] = C[i][i] = BigInteger.ONE;
            for (int j = 1; j < i; j++)
                C[i][j] = C[i-1][j].add(C[i-1][j-1]);
        }
        
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int m = in.nextInt(), n = in.nextInt(), l = in.nextInt();
            if (l > m) { System.out.println("mukyu~"); continue; }
            
            BigInteger total = BigInteger.valueOf(n).pow(m);
            
            for (int i = 0; i <= n; i++)
                for (int j = 0; j <= m; j++)
                    dp[i][j] = BigInteger.ZERO;
            dp[0][0] = BigInteger.ONE;
            
            for (int i = 1; i <= n; i++)
                for (int j = 0; j <= m; j++)
                    for (int k = 0; k <= j && k < l; k++)
                        dp[i][j] = dp[i][j].add(
                            dp[i-1][j-k].multiply(C[m - (j-k)][k])
                        );
            
            BigInteger good = total.subtract(dp[n][m]);
            BigInteger g = good.gcd(total);
            System.out.println(good.divide(g) + "/" + total.divide(g));
        }
    }
}