【HDU4652】Dice 题解

Link

对于第 \(1\) 问

给定一个 \(m\) 个面的骰子，询问求丢多少次使得最后丢的 \(n\) 次都相同的期望

设 \(f(x)\) 为丢了 \(i\) 次恰好结束的概率生成函数，\(g(x)\) 为丢了 \(i\) 次还没结束的概率生成函数。

答案为 \(f'(1)\) 。

\(f(x)+g(x)=g(x)x+1\)

\(g(x)(\frac{1}{m}x)^{n-1}=\sum\limits_{i=1}^nf(x)(\frac{1}{m}x)^{n-i}\)

对 \((1)\) 求导： \(f'(x)+g'(x)=g(x)+xg'(x)\)

代入 \(x=1\) ： \(f'(1)=g(1)\)

对 \((2)\) 代入 \(x=1\) ： \(g(1)(\frac{1}{m})^{n-1}=\sum\limits_{i=1}^n(\frac{1}{m})^{n-i}\)

所以 \(g(1)=\sum\limits_{i=1}^n m^{i-1}\) 。

对于第 \(2\) 问

给定一个 \(m\) 个面的骰子，询问求丢多少次使得最后丢的 \(n\) 次都不同的期望

设 \(f(x)\) 为丢了 \(i\) 次恰好结束的概率生成函数，\(g(x)\) 为丢了 \(i\) 次还没结束的概率生成函数。

答案为 \(f'(1)\) 。

\(f(x)+g(x)=g(x)x+1\)

\(g(x)(\frac{m!}{(m-n)!}x)^{n}=\sum\limits_{i=1}^nf(x)(\frac{1}{m}x)^{n-i}\frac{(n-i)!}{(m-n)!}\)

对 \((1)\) 求导： \(f'(x)+g'(x)=g(x)+xg'(x)\)

代入 \(x=1\) ： \(f'(1)=g(1)\)

对 \((2)\) 代入 \(x=1\) ： \(g(1)(\frac{m!}{(m-n)!})^{n}=\sum\limits_{i=1}^n(\frac{1}{m})^{n-i}\frac{(n-i)!}{(m-n)!}\)

所以 \(g(1)=\sum\limits_{i=1}^n m^{i}\frac{(m-i)!}{m!}\) 。

Code:
注意数据疑似有锅，我用快读就会 TLE ，用 scanf 就能过

#include
using namespace std;
#define pb push_back
#define mp make_pair
#define Fast_IO ios::sync_with_stdio(false);
#define DEBUG fprintf(stderr,"Running on Line %d in Function %s\n",__LINE__,__FUNCTION__)
//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define fir first
#define sec second
#define mod 998244353
#define ll long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
inline int read()
{
	char ch=getchar(); int nega=1; while(!isdigit(ch)) {if(ch=='-') nega=-1; ch=getchar();}
	int ans=0; while(isdigit(ch)) {ans=ans*10+ch-48;ch=getchar();}
	if(nega==-1) return -ans;
	return ans;
}
typedef pair pii;
inline int min(int x,int y,int z){return min(x,min(y,z));}
inline int max(int x,int y,int z){return max(x,max(y,z));}
inline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
inline int add(int x,int y,int z){return add(add(x,y),z);}
inline int sub(int x,int y){return x-y<0?x-y+mod:x-y;}
inline int mul(int x,int y){return 1LL*x*y%mod;}
inline int mul(int x,int y,int z){return mul(mul(x,y),z);}
#define N 1000005
double f[N];
void work()
{
	// int opt=read(),m=read(),n=read();
	int opt,m,n; scanf("%d %d %d",&opt,&m,&n);
	if(opt==0)
	{
		double ans=0; f[1]=1;
		for(int i=2;i<=n;i++) f[i]=f[i-1]*m;
		for(int i=1;i<=n;i++) ans+=f[i];
		printf("%.7lf\n",ans);
	}
	else
	{
		double ans=0;
		f[1]=1;
		for(int i=2;i<=n;i++) f[i]=f[i-1]*m/(m-i+1);
		for(int i=1;i<=n;i++) ans+=f[i];
		printf("%.7lf\n",ans);
	}
}
signed main()
{
	// int T=read();
	int T; scanf("%d",&T);
	while(T--) work();
	return 0;
}