java第二类斯特林数编程代码

斯特林数编程代码"/>

java第二类斯特林数编程代码

题意：有个游戏，两个人玩。有n个卡片，洗牌后放入编号为1到n的盒子里，然后两个人轮流做如下操作，拿出盒子中编号最小的卡片k，然后再去编号为k的盒子中拿出卡片，依次类推，直到没有卡片可拿为止。拿走最后一张卡片的玩家获胜。求先手能够在K次操作以内获胜的概率，(以分数形式输出)

1<=k<=n<=50；

思路：其实就是第一类斯特林数，

第一类Stirling数 s(p,k)

s(p,k)的一个的组合学解释是：将p个物体排成k个非空循环排列的方法数。

s(p,k)的递推公式：s(p,k)=(p-1)*s(p-1,k)+s(p-1,k-1) ,1<=k<=p-1

边界条件：s(p,0)=0 ,p>=1s(p,p)=1  ,p>=0

嗯，这个题就是n张卡排成不大于K的奇数个环排列的方法数，因为说的是先手胜。然后除以N！，因为有n！中洗牌数。

然后最简单的方法就是java大数，奈何我不会，只好网上扒了一段代码充数了，这就去学学java大数。

import java.io.*;

import java.math.*;

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner cin = new Scanner(System.in);

BigInteger dp[][] = new BigInteger[51][51];

BigInteger d[] = new BigInteger[51];

int i, j;

//dp[i][j] = dp[i-1][j] * (i-1) + dp[i-1][j-1]

for(i = 1; i <= 50; i++)

{

dp[i][0] = BigInteger.valueOf(0);

dp[i][i] = BigInteger.valueOf(1);

for(j = 1; j < i; j++)

{

dp[i][j] = dp[i-1][j].multiply(BigInteger.valueOf(i-1));

dp[i][j] = dp[i][j].add(dp[i-1][j-1]);

}

}

d[0] = BigInteger.valueOf(1);

for(i = 1; i <= 50; i++) d[i] = d[i-1] .multiply(BigInteger.valueOf(i));

while(cin.hasNextInt())

{

int n, k;

BigInteger sum, gcd;

n = cin.nextInt();

k = cin.nextInt();

sum = BigInteger.valueOf(0);

for(i = 1; i <= k; i+=2) sum = sum.add(dp[n][i]);

gcd = sum.gcd(d[n]);

System.out.println(sum.divide(gcd)+"/"+d[n].divide(gcd));

}

}

}