首页 > 其他分享 >CF1392H ZS Shuffles Cards

CF1392H ZS Shuffles Cards

时间:2024-06-17 13:59:57浏览次数:23  
标签:frac 重开 ll CF1392H Shuffles ans Cards mod

ZS Shuffles Cards

  • 若我们取到了鬼牌则会游戏重开,这是离谱的
  • 有 \(E(ans)=E(重开多少次)E(重开一次摸的牌数)\)
  • \(E(重开一次摸的牌数)=\frac{n}{m+1}+1\)
    • 考虑每张数字牌在某一次被摸的概率
    • \(P(x)=\frac{1}{m+1}\),因为我们只需考虑所有鬼牌与那一张数字牌的相对位置
    • \(E(...)=nP(x)+1\),加的 \(1\) 是最后摸鬼牌结束
  • \(E(重开多少次)\):
    • 我们借助选牌时选到鬼牌后重开来计算期望
    • 设 \(f(i)\) 表示我们还有 \(i\) 张牌没被取走 \(i\) 的期望
    • \(f(n)=1\),开局的算一次吧
    • \(f(i-1)=\frac{i}{m+i}f(i)+\frac{m}{m+i}(f(i-1)+1)\)
    • \(f(i-1)=f(i)+\frac{m}{i}\)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
ll f[2000200];
ll ksm(ll a,ll b)
{
    ll ans=1;
    while(b){if(b&1)ans=ans*a%mod;b>>=1;a=a*a%mod;}
    return ans;
}
#define inv(x) ksm(x,mod-2)
int main()
{
    ll n,m; cin>>n>>m; f[n]=1;
    for(int i=n;i>=1;i--)
    f[i-1]=(f[i]+m*inv(i))%mod;
    cout<<(n*inv(m+1)+1)%mod*f[0]%mod<<'\n';
    return 0;
}

标签:frac,重开,ll,CF1392H,Shuffles,ans,Cards,mod
From: https://www.cnblogs.com/LUHCUH/p/18252235

相关文章

  • CF1278F Cards(斯特林数+二项式定理)
    题意简述有\(m\)张牌,其中有一张是王牌。你现在可以洗\(n\)次牌(每种牌堆序列等概率出现),然后查看牌堆顶的第一张牌。设\(x\)为\(n\)次洗牌中第一张牌是王牌的次数,则得分为\(x^k\)。求得分的期望值对\(998244353\)取模的值。\(1\len,m<998244353,k\le5000\)分析将......
  • Two Sided Cards 题解
    前言五一网课的例题,但是网上没有详细的题解(真的连题解都找不到啊),所以来写一篇,就当攒RP了。题目可以在这里提交。原题是TopCoder-10947,但是有了账号也交不了?题目简述有\(n\)张卡片,正面和反面分别组成了\(1\simn\)的排列。现在你需要将这\(n\)张卡片排成一排。卡片......
  • CF1392H ZS Shuffles Cards 题解
    题目传送门前置知识概率DP解法设\(f_{i}\)表示有\(i\)张数字牌没进入\(S\),即\(S\)中只有\(n-i\)张数字牌时的期望轮数,有\(f_{i}=\frac{i}{i+m}f_{i-1}+\frac{m}{i+m}(f_{i}+1)\),解得\(f_{i}=f_{i-1}+\frac{m}{i}\),边界为\(f_{0}=1\)。由于每一张数字牌在joke......
  • ARC111B Reversible Cards 题解 (套路题)
    考虑将\(a_i,b_i\)之间连边,发现题目可以被转化为给定一个图,要求对于每条边将其一个顶点染色,问最多能将多少个点染色。于是我们对于每个连通块分开来考虑。对于一个连通块,注意到我们不能将每个顶点染色当且仅当这个连通块是树,且此时可以染色的定点数量为连通块大小减一,如下:如......
  • [Codeforces] CF1740D Knowledge Cards
    CF1740DKnowledgeCards题意有一个\(n\timesm\)的棋盘。现在\((1,1)\)中有一个栈,你可以按照一定的顺序进行出栈操作,每次都可以移动一个卡片到一个相邻的空白位置,但是卡片不能重合。问,能否通过若干次操作,将\((1,1)\)中全部的卡片移动到\((n,m)\)的栈中并使得这个栈按照从栈......
  • MQTT 主题通配符和过滤器Topic Wildcards & Topic Filters
    主题名称中引入了级别分隔符/,用于分割主题级别,如果存在,它将主题名称划分为多个“主题级别”。订阅的主题过滤器可以包含特殊的通配符,可以一次订阅多个主题。特殊字符的通配符可以用在订阅过滤器中,但是不能用于主题名称1.主题级别"/"用于分割主题级别,并为主题名称提供......
  • Cards
    分析本题主要考察思维和简单的数学能力。根据题意我们要尽可能的使得0连续,2分散因为$12+12>(1+1)^2$,反之同理。所以我们尽可能使得最后的形式是2020...00...002即是用0,将2分割开来。首先我们从让一整段0将2分割成两段的情况开始讨论。此时有一整段0长度为$n$......
  • UVA1435 Business Cards 题解
    题目链接思路一道找规律思维题,代码非常简单。能否把\(c\timesd\)的矩阵分成若干个\(a\timesb\)的矩阵,其实就是问你\(a\)或\(b\)中有没有\(c\)或\(d\)的因数。只要存在一组,即可分割成题目所要求的矩阵,输出YES;反之,输出NO。注意:其实每个测试点都有多组数据,但题......
  • ZS Shuffles Cards 题解
    ZSShufflesCards题解我们把每一次抽一些数字牌再抽到joker视作一局游戏。每局期望轮数首先考虑\(f_i\)表示每一局游戏抽出\(i\)张牌的概率。那么就是先抽出\(i-1\)张数字牌,再抽出一张joker。概率就是:\[f_i=\fracm{n+m-i+1}\prod_{k=0}^{i-2}......
  • t113-c-i2s学习篇(cards)
    学习一下t113的i2s驱动1.模块功能规格介绍一堆看不懂的名词,处于半看懂半看不懂的状态2.模块源码结构介绍又是一堆看不懂的文件名字,还是不懂怎么用3.模块配置介绍3.1DeviceTree配置介绍什么是dmic?硬件接口之DMIC 举例,以i2s为例子:3.2board.dts板级配置介绍......