Dice
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 577 Accepted Submission(s): 412
Special Judge
Problem Description You have a dice with m faces, each face contains a distinct number. We assume when we tossing the dice, each face will occur randomly and uniformly. Now you have T query to answer, each query has one of the following form:
0 m n: ask for the expected number of tosses until the last n times results are all same.
1 m n: ask for the expected number of tosses until the last n consecutive results are pairwise different.
Input The first line contains a number T.(1≤T≤100) The next T line each line contains a query as we mentioned above. (1≤m,n≤10 6) For second kind query, we guarantee n≤m. And in order to avoid potential precision issue, we guarantee the result for our query will not exceeding 10 9 in this problem.
Output For each query, output the corresponding result. The answer will be considered correct if the absolute or relative error doesn't exceed 10 -6.
Sample Input
6
0 6 1
0 6 3
0 6 5
1 6 2
1 6 4
1 6 6
10
1 4534 25
1 1232 24
1 3213 15
1 4343 24
1 4343 9
1 65467 123
1 43434 100
1 34344 9
1 10001 15
1 1000000 2000
Sample Output
1.000000000
43.000000000
1555.000000000
2.200000000
7.600000000
83.200000000
25.586315824
26.015990037
15.176341160
24.541045769
9.027721917
127.908330426
103.975455253
9.003495515
15.056204472
4731.706620396
Source 2013 Multi-University Training Contest 5
一维dp。dp[n]=0,则可以列出之前的dp[n-1],dp[n-2]...dp[2],dp[1],dp[0]的dp方程,根据相互转化的方式,可以将式子一个个向上带入,最后求出公式。
具体而言,这位老哥的题解写的很明白。
#include <cstdio>
#include <iostream>
#include <string.h>
#include <string>
#include <map>
#include <queue>
#include <deque>
#include <vector>
#include <set>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <stack>
#include <iomanip>
#define mem0(a) memset(a,0,sizeof(a))
#define meminf(a) memset(a,0x3f,sizeof(a))
using namespace std;
typedef long long ll;
typedef long double ld;
typedef double db;
const int maxn=1000005,inf=0x3f3f3f3f;
const ll llinf=0x3f3f3f3f3f3f3f3f;
const ld pi=acos(-1.0L);
db dp[maxn];
int main() {
int cas;
while (scanf("%d",&cas)!=EOF) {
while (cas--) {
int i,n,m,t;
scanf("%d%d%d",&t,&m,&n);
if (t==0) {
int ans=1;
for (i=1;i<n;i++) {
ans=ans*m+1;
}
printf("%d.000000000\n",ans);
} else {
db ans=0.0,p=1.0;
for (i=1;i<=n;i++) {
ans+=p;
p*=(db)m/(db)(m-i);
}
printf("%.9lf\n",ans);
}
}
}
return 0;
}