F - Lottery

本文主要是介绍F - Lottery，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门：ATC

正文：

此题是一道很妙的dp题。

总所周知，动态规划有两大难点，第一是想到这是一道dp题，第二是想到正确的状态转移方程

首先想聊聊怎么想到此题可以用dp来解：我们在想题目的时候，可以想往最暴力的方式去想，想想这题可不可以通过枚举求得正确答案，如果可以，那么此题就可能可以用dp求解，然后再想想不同项之间存不存在状态转移关系（~~一般想不出来~~），如果存在就是dp了。

回到此题，可以明显发现此题可以通过枚举状态来得到正确答案，所以我们的目标就变成找到状态转移式子。

题目给出三个变量： n ， m , k 。

题意可以用中文翻译成（原题是摸彩票，但我觉得没有涂颜色直观）：一共有n种颜色，每种颜色有相应的出现概率，现在要在k张纸上涂色，问k张纸上有m种不同颜色的概率是多少？

我们先设 $dp[n][m][k]$ 为答案（注意是先假设，在后面的分析中，其含义会改变）。

第一步：我们想一想 $dp[n][m][k]$ 和 $dp[n][m][k - 1]$ 之间有没有一种联系。这种情况可以理解成加了一张纸，所以只要保证新加入的这张纸是m种颜色之一就行。

所以 $dp[n][m][k] = dp[n][m][k - 1] * (\sum _{i = 1} ^ mp(i))$ 其中 $p(i)$ 只选择的第i号颜色出现的概率。

这个状态转移方程有没有用，我也不知道，我觉得应该没什么用，因为我无法确定我选择了哪m种颜色，所以这个方程不能直接转移，但是先不管那么多，先把方程列在这里罢了。

第二步：我们想一想 $dp[n][m][k]$ 和 $dp[n][m- 1][k]$ 之间有没有一种联系。这种情况不用多说，不用深入思考，就可以发现情况很复杂（以我的脑子肯定分析不来），所以直接就跳过吧。

第三步：我们想一想 $dp[n][m][k]$ 和 $dp[n-1][m][k]$ 之间有没有一种联系。这种情况可以直观的理解成加了一种选择的颜色。

可以分两种情况考虑了：

情况一：如果这个颜色我压根就不选，那么 $dp[n][m][k] = dp[n-1][m][k]$ 。

情况二：我选择了这个颜色，也就是说，纸张上的颜色要加一，即 $dp[n][m][k]$ 和 $dp[n-1][m][k]$ 之间是不存在关系了，但是 $dp[n][m][k]$ 和 $dp[n-1][m-1][k]$ 之间建立了新的联系。

我们进一步思考，如果加进去了新的颜色 c ，那么染成颜色c的纸张的个数明显会影响答案，我们假设新加入了kk张染有颜色c的纸，现在的关键点就变成了处理 $dp[n][m][k]$ 和 $dp[n-1][m-1][k-kk]$ 之间的关系。

在之前，我们对dp的定义是答案。但现在要做出改变，这个改变我认为是此题最妙的点。

如果dp是答案的话，明显，这个结果是打乱了的，什么意思呢，我们假设现在有4张纸，有2种颜色（R and B），那么dp的结果应该是出现以下情况的概率之和：

RBBB,BRBB,BBRB,BBBR,RRBB,RBRB,RBBR,BRRB,BRBR,BBRR,RRRB,RRBR,RBRR,BRRR

如果这时候我们要在里面加一张纸，且这张纸的颜色不是R和B，显然，我们是无法对其进行去重的，也就是无法通过已有的方案数去确定所有可能的情况。

但是我们可以换一个角度去思考问题：

上面的所有可能一共可以分解成如下三种情况

一：RBBB 的所有排列组合= $\frac{4!}{1!*3!}+\frac{4!}{2!*2!}+\frac{4!}{1!*3!}$

二：RRBB的所有排列组合= $\frac{4!}{2!*2!}$

三：RRRB的所有排列组合= $\frac{4! }{1!*3!}$

假设我们新加入p张染有颜色c的纸张，我们的方案数应该为：

$\frac{(4+p)! }{1!*3!*p!}+\frac{(4+p)! }{2!*2!*p!}+\frac{(4+p)! }{1!*3!*p!}$

这时候神奇的事情发生了，可见分子一定是纸张的个数的阶乘，而分子则是每种颜色的个数的阶乘。

如果我们以 $dp[n][m][k]*k!$ 为答案， $dp[n][m][k]$ 和 $dp[n-1][m-1][k-kk]$ 之间就存在如下关系：

$dp[n][m][k] =\frac{ dp[n-1][m-1][k-kk] * p(n) ^{kk} }{kk!}$

因为kk是属于一个范围的，所以正确的状态转移方程可以写成：

$dp[n][m][k] =\sum \frac{ dp[n-1][m-1][k-kk] * p(n) ^{kk} }{kk!}$

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define  ll long long
const int mod = 998244353; 
ll ksm(ll a, ll b){ll kase = 1;while(b){if(b & 1){kase = kase * a % mod;}a = a * a % mod;b >>= 1 ;}return kase ;
}
ll ni(ll x){return ksm(x,mod-2);
}
ll dp[51][51][51];
int main(){ios::sync_with_stdio(false);cin.tie(0);int n , m ,k;cin>>n>>m>>k;vector<ll>w(n);for(int i = 0;i < n; i++){cin>>w[i];}ll sum = accumulate(w.begin(),w.end(),(ll)0);sum = ni(sum);for(int i = 0;i < n; i++){w[i] = w[i] * sum % mod; }vector<ll>fac(k+1);fac[0] = 1;for(int i = 1; i <= k;i++)fac[i] = fac[i -1 ] * i % mod;for(int i = 0 ; i <= n ;i++)dp[i][0][0]=1;for(int i = 1;i <= n;i++){for(int j = 1;j <= m ;j ++){for(int x = j ; x <= k;x++){for(int y = 0; y <= x - j + 1; y++){if(y == 0)dp[i][j][x] = (dp[i][j][x] + dp[i-1][j][x]) % mod;else {dp[i][j][x] += dp[i - 1][j - 1][x - y] * ksm(w[i - 1],y) % mod * ni(fac[y]) % mod;dp[i][j][x] %= mod;}}}}}cout<< dp[n][m][k] * fac[k] % mod<<'\n';return 0;
}

这篇关于F - Lottery的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！