首页 > 其他分享 >[ARC061F] Card Game for Three

[ARC061F] Card Game for Three

时间:2024-04-10 09:24:25浏览次数:28  
标签:aligned dbinom sum Three 玩家 Game ARC061F n2 n3

题意

有 \(3\) 个人。每个人分别有 \(n1, n2, n3\) 张牌。

每张牌上有一个名字,分别表示三个人。

对于每个回合,进行如下操作:

  • 若当前回合的玩家手上没有牌了,则该玩家获胜。
  • 否则从手牌中取出一张牌,丢弃她,并进入该牌上的名字的玩家的回合。

求第一名玩家获胜的牌的分配方案数。

Sol

很简单的数数题。

首先考虑对于这个问题建立一个双射。

不难想到可以考虑确定当前牌的 丢弃序列 \(S\)。

注意到因为某个玩家获胜后,对于别的玩家来说牌会有剩余。

因此可以考虑使用 \(m\) 记录当前的 \(|S|\)。

显然序列 \(S\) 包含 \(n1\) 个 \(1\),考虑枚举当且序列中,非 \(1\) 数的个数。

不难列出:

\[\sum_{k = 0} ^ {n2 + n3} 3 ^ {n2 + n3 - k} \dbinom{k + n1 - 1}{k} \sum_{i = 0} ^ k [i \le n2][k - i \le n3] \dbinom{k}{i} \]

考虑设

\[\begin{aligned} f(k) = \sum_{i = k - n3} ^ {n2} \dbinom{k}{i} \end{aligned} \]

注意到下指标求和很不好做,但是这个式子的形式十分优美,考虑递推。

\[\begin{aligned} &= \sum_{i = k - n3} ^ {n2} \dbinom{k - 1}{i} + \dbinom{k - 1}{i - 1} \\ &= \sum_{i = k - n3} ^ {n2} \dbinom{k - 1}{i} + \sum_{i = k - n3 - 1} ^ {n2 - 1} \dbinom{k - 1}{i} \end{aligned} \]

注意到这两个东西和 \(f(k - 1)\) 很像,左边显然少一个 \(\dbinom{k - 1}{k - n3 - 1}\),右边少一个 \(\dbinom{k - 1}{n2}\)。

因此

\[f(k) = 2f(k - 1) - \dbinom{k - 1}{n2} - \dbinom{k - 1}{k - n3 - 1} \]

做完了。

时间复杂度:\(O(n)\)。

标签:aligned,dbinom,sum,Three,玩家,Game,ARC061F,n2,n3
From: https://www.cnblogs.com/cxqghzj/p/18125328

相关文章

  • three.js尝试渲染gbl模型成功!(三)
    参照教程:https://cloud.tencent.com/developer/article/2276766?areaSource=102001.5&traceId=88k805RaN_gYngNdKvALJ(作者:九仞山)通过最近两天查three.js入门教程了解到这玩应支持包括.obj、.gltf等类型的模型结构。glTF(GL传输格式)是Khronos的一个开放项目,它为3D资产提......
  • three.js零基础入门超全超细的教程整理(一)
    事情是这样的:有一天我干完活看技术文章发现了three.js诶!这玩应挺有意思盘盘于是第一天找教程上官网初上手第二天找案例渲模型试VR第三天捋文档然后来活了没时间捋了下面是集百家精华教程的整理总结涉及到教程方面有加源作者和地址超详细的教程:http://ww......
  • ConvexPolygonGame
    博弈#计算几何这要先手可以操作,那么一定存在必胜策略所以题目转化为判原来的多边形内有没有三个不共线的点把所有点求出来判共线即可//Author:xiaruizeconstintINF=0x3f3f3f3f3f3f3f3f;constintMOD=1000000007;constintN=2e5+10;intn;piia[N];int......
  • three.js基础之几何体颜色、纹理贴图、外部模型
    几何体颜色<body><canvasid="mainCanvas"width="400px"height="300px"></canvas></body><scripttype="importmap">{"imports":{"three":"./js/build/......
  • three.js基础之动画、相机、材质、灯光
    动画<body><canvasid="mainCanvas"width="400px"height="300px"></canvas></body><scripttype="importmap">{"imports":{"three":"./js/build/thr......
  • three.js基础之几何体Curve、Geometry
    CurveEllipseCurve<canvasid="EllipseCurve"width="300px"height="200px"></canvas><canvasid="ArcCurve"width="300px"height="200px"></canvas><canvasid="Curv......
  • three.js基础
    记录下three.js的学习历程。three.js基本概念包括画布Canvas、渲染器Renderer、场景Scene、相机Camera、光源Light、几何体Geometry、材质Material、颜色纹理、点模型、线模型、网格模型、阴影、外部三维模型、动画等 基础<canvasid="basic"></canvas><scripttype="impo......
  • HTB-Three
    HTB-Three1.TASK1输入命令:nmap-sS-sV10.129.247.144-sC使用默认脚本扫描-sV探测服务/版本信息答案:22.TASK2问题:网站“联系人”部分提供的电子邮件地址的域是什么?答案:thetoppers.htb3.TASK3问题:在没有DNS服务器的情况下,我们可以使用哪个Linux文件将主机名......
  • CodeForces 1942E Farm Game
    洛谷传送门CF传送门不妨假设先手的牛在后手的牛左边,右边是对称的。直接给出结论:先手必败当且仅当全部\(b_i-a_i\)为奇数。证明考虑归纳,首先\(\foralli\in[1,n],b_i-a_i=1\)是必败态,因为先手只能往左退,最后后手会把先手逼到最左边使得它无法动弹。然后若存在......
  • 安装Pygame过程中提示错误WARNING: Retrying…ERROR: Exception: Traceback…WARNING:
    安装Pygame过程中提示错误WARNING:Retrying…ERROR:Exception:Traceback…WARNING:Youareusingpipversion解决方案前言Pygame错误错误分析解决方案错误分析结论更新pip安装Pygame前言输入Pygame安装命令pipinstallpygame安装Pygame出错提......