2020-2021:teams:wangzai_milk:codeforce_1392部分题解
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:wangzai_milk:codeforce_1392部分题解 [2020/09/03 19:25] infinity37 [1392G] |
2020-2021:teams:wangzai_milk:codeforce_1392部分题解 [2020/09/03 19:34] (当前版本) infinity37 [1392H] |
||
|---|---|---|---|
| 行 183: | 行 183: | ||
| ==== 1392H ==== | ==== 1392H ==== | ||
| ===题意=== | ===题意=== | ||
| + | 给你$n$张数字牌和$m-n$张特殊牌河一个数字集合。进行如下操作： | ||
| + | |||
| + | 拿出最上面的那张卡片，如果卡片是数字牌，那么把这个数字放进集合。 | ||
| + | |||
| + | 其他情况下把所有卡片重新打乱。检验集合是否包含了所有数字，如果包含了结束游戏。 | ||
| + | |||
| + | 问期望操作次数。 | ||
| ===题解=== | ===题解=== | ||
| + | 期望操作次数是期望游戏轮数乘以期望每一轮次数。 | ||
| - | ===代码=== | + | 可以发现如果在游戏中摸到特殊牌那么一轮就会结束，那么我们算出所有排列中第一张特殊牌之前的牌数，然后+1除以排列数目就是每轮游戏操作次数的期望。这个的答案是$\frac{n}{m+1}+1$。 |
| + | 然后另一个部分则是$m\sum_{i=1}^n\frac{1}{i}+1$，最终答案就是这两者相乘。 | ||
| + | |||
| + | ===代码=== | ||
| + | <hidden><code c++> | ||
| + | #include <bits/stdc++.h> | ||
| + | using namespace std; | ||
| + | typedef long long ll; | ||
| + | const int mod = 998244353; | ||
| + | ll quick_pow(ll x,ll y) { | ||
| + | ll ans = 1; | ||
| + | while (y) { | ||
| + | if (y&1) ans = ans*x%mod; | ||
| + | x = x*x%mod; | ||
| + | y >>= 1; | ||
| + | } | ||
| + | return ans; | ||
| + | } | ||
| + | int main() { | ||
| + | int n,m; | ||
| + | scanf("%d%d",&n,&m); | ||
| + | ll ans1 = (1ll*n*quick_pow(m+1,mod-2)%mod+1)%mod; | ||
| + | ll ans2 = 0; | ||
| + | for (int i = 1;i<= n;i++) | ||
| + | ans2 = (ans2+quick_pow(i,mod-2))%mod; | ||
| + | ans2 = (ans2*m+1)%mod; | ||
| + | printf("%lld\n",ans1*ans2%mod); | ||
| + | return 0; | ||
| + | } | ||
| + | </code></hidden> | ||
| \\ | \\ | ||
2020-2021/teams/wangzai_milk/codeforce_1392部分题解.1599132328.txt.gz · 最后更改: 2020/09/03 19:25 由 infinity37
