題意：

m個位置，每個位置可以等概率填n種數(shù)，規(guī)定一個數(shù)字出現(xiàn)次數(shù)不能超過L次（注意不是連續(xù)L次），填完m個位置后滿足約束的概率是多少。

思路：

定義dp[i][j]為前i種數(shù)字填充j個位置（j個位置不必連續(xù)）的方案數(shù)，那么

dp[i][j]=∑(1<=k&&k<L&&k<=j)dp[i-1][j-k]*C[m-(j-k)][k],C為組合數(shù)

結果就是(n^m-dp[n][m])/n^m

import java.util.*; import java.io.*; import java.math.*; public class Main {static BigInteger [][] C = new BigInteger [110][110];static BigInteger [][] dp = new BigInteger [110][110];public static void main(String [] args) {Scanner cin = new Scanner(new BufferedInputStream(System.in));C[0][0] = BigInteger.ONE;for (int i = 1; i <= 100; 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]);}}int m, n, l;while (cin.hasNext()) {m = cin.nextInt(); n = cin.nextInt(); l = cin.nextInt();if (l > m) {System.out.println("mukyu~");continue;}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 < l && k <= j; k++) {dp[i][j] = dp[i][j].add(dp[i-1][j-k].multiply(C[m-(j-k)][k]));}}}BigInteger y = BigInteger.valueOf(n).pow(m);BigInteger x = y.subtract(dp[n][m]);BigInteger z = x.gcd(y);x = x.divide(z);y = y.divide(z);System.out.println(x+"/"+y);}cin.close();} }

?

總結

以上是生活随笔為你收集整理的ZOJ 3380 Patchouli's Spell Cards——组合数+概率dp的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。