ZOJ-3329 one person game 题解

题目链接

题目大意

题面

\(3\) 个骰子，分别有 \(k1\) 、 \(k2\) 、\(k3\) 面，且骰子掷到某一面的 概率 是相等的。

设 \(3\) 个骰子各掷一次 称作 一轮操作， 每一轮操作会有以下两种情况

·当 \(k1\) 面的骰子的点数为 \(a\) ， \(k2\) 面的骰子的点数为 \(b\) ， \(k3\) 面的骰子的点数为 \(c\) 时，累加器清零。

·否则，累加器累加三个骰子的点数。

求当累加器大于 \(n\) 时，需要操作的轮数的期望。

输入

第一行一个数 \(T\) ，一共 \(T\) 组数据

下面一共 \(T\) 行，每行 \(7\) 个数，分别为 \(n\) 、 \(k1\) 、 \(k2\) 、 \(k3\) 、 \(a\) 、 \(b\) 、 \(c\)

输出

一共 \(T\) 行，即答案

题意分析

这道题涉及了 概率与期望 。大家没有过多的了解，没有关系，你可以在小编Blog中看到《[数论]概率与期望》的讲解。

我们知道， \(E{(X)} = \sum P{(i)} \times X{(i)}\) ，也就是 \(E{(X)} = \sum \text{概率} \times \text{权值}\)

我们 通常 使用 \(DP动规\) 来解决 概率与期望 问题

设 \(dp[i]\) 表示累加器为 \(i\) 时，还需要的轮数的期望。 那么我们来列举 \(dp[i]\) 进行操作后的结果对应的期望值

不妨设 清零计数器 的结果为 情况一 ，其他 为 情况二 。

那么情况一的概率 \(P{(0)}\) 易得 \(\frac{1}{k1 \times k2 \times k3}\)

情况二的概率 \(P{(k)}\) 由于 \(k\) 的变化，预处理即可

情况一的期望为 \(P{(0)} \times dp[0]\)
情况二的期望为 \(\sum_{k = 3}^{k\leq k1+k2+k3} ((A[i + k] \times dp[0] + B[i + k]) \times P{(k)})\)

那么得到 状态转移方程 \(dp[i] = P{(0)} \times dp[0] + \sum_{k = 3}^{k\leq k1+k2+k3} (dp[i+k] \times P{(k)}) + 1\)

为什么\(+1\)

新掷一轮的次数也要加进去

为什么刚才是 \(dp\) ，现在又跳到待定系数法来了？

我们发现，刚才列的状态转移方程的 \(dp[0]\) 是 有后效性

有后效性还叫dp？

这时候我们就要用到待定系数法了。其实还可以使用高斯消元，只是因为高斯消元时间复杂度过高，故采用待定系数法

我们知道，对于一个一次函数而言，基本形式都是 \(y = a \times x + b\)

我们设两个系数数组： \(A[]\) 和 \(B[]\)

那么 \(dp[i]\) 可以表示为 \(A[i] \times dp[0] + B[i]\)，即

\(dp[i] = A[i] \times dp[0] + B[i]\)，标号①

同理得

\(dp[i + k] = A[i + k] \times dp[0] + B[i + k]\) 标号②

将①和②带入状态转移方程得

\(A[i] \times dp[0] + B[i] = P{(0)} \times dp[0] + \sum((A[i + k] \times dp[0] + B[i + k]) \times P{(k)}) + 1\)

此时将等式右边的西格玛拆开，得

\(A[i]\times dp[0]+B[i]=P{(0)} \times dp[0] + \sum(A[i + k] \times dp[0] \times P{(k)}) + \sum(B[i + k] \times P{(k)}) + 1\)

这时候发现，等式两边的 \(dp[0]\) 可以对应起来，使得等式左边 \(dp[0]\) 的系数 \(A[i]\) ，可以与右边的 \(\sum(A[i+k] \times P{(k)})\) 与 \(P{(0)}\) 两个系数对应起来，得

\(A[i] = P{(0)} + \sum_{k = 3}^{k \leq k1+k2+k3}(A[i+k] \times P{(k)})\)

同理对应 \(B[i]\) 系数，得

\(B[i] = \sum_{k = 3}^{k \leq k1+k2+k3}(B[i+k] \times P{(k)}) + 1\)

转换问题

我们按照之前的 \(dp[]\) 定义，那么 \(dp[0]\) 将是我们的答案。得

\(dp[0] = A[0] \times dp[0] + B[0]\)

将 \(dp[0]\) 项都移到左边，化简后得

\(dp[0] = \frac{B[0]}{1 - A[0]}\)

于是我们从求 \(dp[]\) 转换为求 \(A[]\) 与 \(B[]\)

怎么求 \(A[]\) 和 \(B[]\)

\(A[i] = P{(0)} + \sum_{k = 3}^{k \leq k1+k2+k3}(A[i+k] \times P{(k)})\)

\(B[i] = \sum_{k = 3}^{k \leq k1+k2+k3}(B[i+k] \times P{(k)}) + 1\)

像原本求 \(dp[]\) 一样，逆序按照递推公式枚举解决即可

代码

#include
#include
#pragma GCC optimize(2)
#define in(a) a = read()
#define out(a) write(a)
#define outn(a) out(a),putchar('\n')
#define ll long long
#define rg register
#define New int
using namespace std;
namespace IO_Optimization{
	inline New read()
	{
	    New X = 0,w = 0;
		char ch = 0;

		while(!isdigit(ch))
		{
			w |= ch == '-';
			ch=getchar();
		}
	    while(isdigit(ch))
		{
			X = (X << 3) + (X << 1) + (ch ^ 48);
			ch = getchar();
		}
	    return w ? -X : X;
	}

	inline void write(New x)
	{
	     if(x < 0) putchar('-'),x = -x;
	     if(x > 9) write(x/10);
	     putchar(x % 10 + '0');
	}

	#undef New
}
using namespace IO_Optimization;

const int MAXN = 600;

double p[MAXN],A[MAXN],B[MAXN];
int n,k1,k2,k3,a,b,c,T;

int main()
{
    in(T);
    while(T--)
    {
        memset(p, 0, sizeof(p));
        memset(A, 0, sizeof(A));
        memset(B, 0, sizeof(B));//多组数据清空数组 
        in(n),in(k1),in(k2),in(k3),in(a),in(b),in(c);//输入 
		int tmp = k1 * k2 * k3;//这个地方纯属优化常数 
        p[0] = 1.0 / tmp; //p[0]
        for(rg int i = 1;i <= k1; ++i) //三重循环预处理所有的概率P(i) 
            for(rg int j = 1;j <= k2; ++j)
                for(rg int k = 1;k <= k3; ++k)
                {
                    if(i == a && j == b && k == c) //归零的概率不要累加 
                        continue;
                    p[i+j+k] += p[0];	
                }
        for(rg int i = n;i >= 0; --i)
        {
            for(rg int j = 3; j <= tmp; ++j)
            {
                A[i] += A[i+j] * p[j]; 
                B[i] += B[i+j] * p[j];
            }
            A[i] += p[0]; //A[i] = sigma()  + p0
            B[i] += 1; //B[i] = sigma() + 1
        }
        printf("%.15lf\n",B[0] / (1-A[0]));
    }
    return 0;
}