首页 > 代码库 > UVA10759_Dice Throwing
UVA10759_Dice Throwing
求掷骰子n次,点数之和超过m的概率有多大?分数表示。
两种方法:
1、直接DP。用两个数组分别表示分子和分母,注意计算过程中时时约分。
2、将(x1+x2+x3+x4+x5+x6)n多项式展开,把大于m的幂的系数累加,比上所有项系数的总和就是答案了。这个理解也很容易。
召唤代码君:
#include <iostream>#include <cstdio>#include <cstring>typedef long long ll;using namespace std;ll f1[25][150],f2[25][150];ll sum1[25][150],sum2[25][150];int n,m;ll gcd(ll A,ll B){ return B==0?A:gcd(B,A%B);}ll lcm(ll A,ll B){ return A/gcd(A,B)*B;}int main(){ f1[0][0]=f2[0][0]=sum1[0][0]=sum2[0][0]=1; for (int i=1; i<25; i++) for (int j=i; j<=i*6; j++)//i times score j { ll F1=0,F2=1,FF; for (int k=max(j-6,0); k<j; k++) { if (f1[i-1][k]==0) continue; FF=lcm(F2,f2[i-1][k]*6); F1=F1*(FF/F2)+f1[i-1][k]*(FF/(f2[i-1][k]*6)); F2=FF; FF=gcd(F1,F2); F1/=FF,F2/=FF; } f1[i][j]=F1,f2[i][j]=F2; if (i==j) { sum1[i][j]=f1[i][j],sum2[i][j]=f2[i][j]; continue; } FF=lcm(sum2[i][j-1],f2[i][j]); F1=sum1[i][j-1]*(FF/sum2[i][j-1])+f1[i][j]*(FF/f2[i][j]); sum1[i][j]=F1,sum2[i][j]=FF; FF=gcd(sum1[i][j],sum2[i][j]); sum1[i][j]/=FF,sum2[i][j]/=FF; } while (scanf("%d%d",&n,&m) && (n|m)) { if (m<=n) puts("1"); else if (m>6*n) puts("0"); else printf("%lld/%lld\n",sum2[n][m-1]-sum1[n][m-1],sum2[n][m-1]); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。