通道

題意：有m個位置，每個位置填入一個數，數的范圍是1~n,問至少有L個位置的數一樣的概率

思路：

總數是n^m，我們求沒有L個位置一樣的數的概率* 設 dp[i][j]表示用前i個數，填充j個位置的方案數（要符合沒有L個位置是一樣的數)* dp[i][j]=dp[i-1][j]+Sigm( dp[i-1][j-k]*C[m-(j-k)][k] ) k<=j&&k<L* 其實就是看第i個數，可以不填，填一個位置，兩個位置······這樣累加過來。* 那么最后的答案就是 (n^m-dp[1~n][m])/(n^m)

代碼：

import java.util.*; import java.io.*; import java.math.*; public class Main {static BigInteger[][] dp=new BigInteger[110][110];static BigInteger[][] C=new BigInteger[110][110];//組合數public static void main(String arg[]){Scanner cin=new Scanner(new BufferedInputStream(System.in));for(int i=0;i<105;i++){C[i][0]=C[i][i]=BigInteger.ONE;for(int j=1;j<i;j++)C[i][j]=C[i-1][j-1].add(C[i-1][j]);}int N,M,L;while(cin.hasNext()){M=cin.nextInt();N=cin.nextInt();L=cin.nextInt();BigInteger tol=BigInteger.valueOf(N).pow(M);if(L>M){System.out.println("mukyu~");continue;}if(L>M/2)//這個時候可以直接用組合數求出來 {BigInteger ans=BigInteger.ZERO;for(int i=L;i<=M;i++)ans=ans.add(C[M][i].multiply(BigInteger.valueOf(N-1).pow(M-i)));ans=ans.multiply(BigInteger.valueOf(N));BigInteger gcd=ans.gcd(tol);System.out.println(ans.divide(gcd)+"/"+tol.divide(gcd));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=1;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 ans=BigInteger.ZERO;for(int i=1;i<=N;i++)ans=ans.add(dp[i][M]); ans=tol.subtract(ans);BigInteger gcd=ans.gcd(tol);System.out.println(ans.divide(gcd)+"/"+tol.divide(gcd));}} } View Code

?

轉載于:https://www.cnblogs.com/Rojo/p/4725492.html

總結

以上是生活随笔為你收集整理的【概率DP】 ZOJ 3380 Patchouli's Spell Cards的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。