更好的阅读体验

C. 自闭的游戏

小S在玩一个自闭的游戏。
有一个骰子，这个骰子有$m$个面分别写着 $1\cdots m$
并且投掷时每面朝上的概率相同。
现在，小S投了这个骰子$n$次，并且告诉小T点数$v$至少出现了一次。
小T需要猜测一个正整数$sum$，表示她猜测的这$n$次骰子的点数之和是多少。
现在，他想要知道玩家的正确率有多少呢？

输入格式

一行四个正整数，分别表示$n,m,v,sum$。

输出格式

一行一个实数，表示猜对的概率。你的答案被认为是正确的，当且仅当绝对或相对精度误差$\le 10^{-6}$。

样例

样例一

input

2 6 6 12

output

0.09090909

样例二

input

2 3 2 4

output

0.20000000

约定与限制

对于$10\%$ 的数据，满足 $1 \le n \le 1$。
对于$40\%$ 的数据，满足 $1 \le n,m \le 20$。
对于$100\%$ 的数据 ，满足 $1 \le n,m \le 50$ ，$1\le v\le m$，$1\le sum\le n\times m$。

时间限制:1s
空间限制:128MB

解题报告

题意理解

有$n$个点，每个点的取值范围是$[1,n]$，已知在这$n$个点中，至少有一个点的值为$v$，将这个$n$个点的和累加，得到值$x$
问：当$x=sum$的时候的取数方案数占总合法取数方案数的比例？

$40pts$思路

我们可以使用暴力搜索，算出每一种方案数，然后再统计合法方案。

代码略

$100pts$思路

我们观察这道题目，发现以下几种性质。

1. 题目并不关心我们的具体方案，只需要方案数（属性为统计）
2. 至少有一个数是$v$ （限制条件）
3. 前面取什么数字，和后面取什么数字并没有任何影响。（无后效性）

那么上面这些性质，就可以保证，这道题目可以使用动态规划算法。

我们接着讨论，如何描述这个状态。

我们发现，这道题目具有明显的线性性质

我们可以把，每一次甩骰子，作为我们的阶段。

$$ f[i] \quad 表示此时选到了第i个数 $$

接着题目关心，我们这些数的和。

$$ f[i][k] \quad 表示此时选到了第i个数，这些数的和是k $$

接着题目的限制条件是，这些数中是否至少有一个数是$v$

$$ f[i][k][0/1] \quad 表示此时选到了第i个数，这些数的和是k \\\\ 0表示没有一个v，1表示至少有一个v $$

那么状态转移方程是什么呢？自然就是我们的背包动态规划的模样了。

假如说，此时我们第$i$个数，他的值是$j$

f[i][k][0]+=f[i-1][k-j][0]
//到目前都没有出现v，那么推来的状态，也不可以出现v 
if (j!=v)//当前选择元素不是v
    f[i][k][1]+=f[i-1][k-j][0]
//现在已经出现v了，而本次没有选择v，那么推来的状态，必须出现过v
if (j==v)
    f[i][k][1]+=f[i-1][k-j][0]+f[i-1][k-j][1];
//因为本次选择了v，之前是否选择v没有限制

代码解析

#include <bits/stdc++.h>
using namespace std;
const int N=52;
int n,m,v,sum;
double f[N][N*N][2];
inline void init()
{
    scanf("%d%d%d%d",&n,&m,&v,&sum);
    f[0][0][0]=1;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            for(int k=max(i,j); k<=i*m; k++)
            {
                f[i][k][j==v]+=f[i-1][k-j][0];
                f[i][k][1]+=f[i-1][k-j][1];
                //这里代码和上面解释是一样的，只不过是不同的写法而已
            }
    double ans=0;
    for(int j=1; j<=n*m; j++)
        ans+=f[n][j][1];//合法方案，要求是必须选择v的
    printf("%.8lf\n",f[n][sum][1]/ans);//保证精度
}
signed main()
{
    init();
    return 0;
}