ZOJ 3380 Patchouli's Spell Cards——组合数+概率dp

题意：

m个位置，每个位置可以等概率填n种数，规定一个数字出现次数不能超过L次（注意不是连续L次），填完m个位置后满足约束的概率是多少。

思路：

定义dp[i][j]为前i种数字填充j个位置（j个位置不必连续）的方案数，那么

dp[i][j]=∑(1<=k&&k

结果就是(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(); }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。