描述
In
the game of Dungeons & Dragons, players often roll multi-sided dice to
generate random numbers which determine the outcome of actions in the game.
These dice come in various flavors and shapes, ranging from a 4-sided
tetrahedron to a 20-sided isocahedron. The faces of an n-sided die, called dn
for short, are numbered from 1 to n. Ideally, it is made in such a way that the
probabilities that any of its n faces shows up are equal. The dice used in the
game are d4, d6, d8, d10, d12, and d20.
When generating random numbers to
fit certain ranges, it is sometimes necessary or desirable to roll several dice
in conjunction and sum the values on their faces. However, we may notice that
although different combinations of dice yield numbers in the same range, the
probabilities of rolling each of the numbers within the range differ entirely.
For example, a d6 and a d10 afford a range of 2 to 16 inclusive, as does two
d8s, but the probability of rolling a 9 differs in each circumstance.
Your
task in this problem is to determine the probability of rolling a certain
number, given the set of dice used.
输入
The input test file will contain multiple cases, with each case on a single line of input. The line begins with an integer d (where 1 ≤ d ≤ 13), the number of dice rolled. Following are d descriptors of dice, which can be any of “d4”, “d6”, “d8”, “d10”, “d12”, or “d20”. The last number on each line is an integer x (where 0 ≤ x ≤ 1000), the number for which you are to determine the probability of rolling with the given set of dice. End-of-input is marked by a single line containing 0; do not process this line.
输出
For each test case, output on a single line the probability of rolling x with the dice, accurate to five decimal places. Note that even if there trailing zeros, you must show them (see Test problem for an example of decimal formatting).
样例输入
1 d10 5
2 d6 d6 1
2 d10 d6 9
2 d8 d8 9
0
样例输出
0.10000 0.00000 0.10000 0.12500
题意：求几个筛子相加==x的概率，母函数问题。
#include <stdio.h> #include <string.h> #define MAXN 13001 __int64 a[MAXN],b[MAXN]; int d[1001]; int main(int argc, char *argv[]) { __int64 n,k,all; while(scanf("%I64d",&n)!=EOF && n){ all=1; for(int i=1; i<=n; i++){ scanf(" d%d",&d[i]); all*=d[i]; } scanf("%I64d",&k); a[0]=1; __int64 sum=0,sum1; for(int i=1; i<=n; i++){ sum1=sum+d[i]; memset(b,0,sizeof(__int64)*(sum1+1)); for(int j=0; j<=sum; j++){ for(int k=1;k<=d[i]; k++){ b[j+k]=b[j+k]+a[j]; } } memcpy(a,b,sizeof(__int64)*(sum1+1)); sum=sum1; } printf("%.5lf\n",double(a[k])/all); } return 0; }