【转载】笑死，还真有根据810975出的题

在逛另一个论坛的时候看到一个有趣的帖子，征得原作者同意后转载过来给大家乐呵一下

原文

首先庆祝下今天CCPC的比赛被队友带着拿了个银
因为是专业性比赛，所以不谈比赛内容，隔行如隔山，就说到挺有意思的题吧。

玩炉石的朋友肯定都知道810975的梗
然后今天打CCPC 威海，还真有道题就是根据这个出的，读到时大伙都乐了
题目大意就是曾有为著名炉石主播在8月10日，进行了9把游戏，赢了7把，其中还有个5连胜。
现在问有多少种情况：玩了n局游戏，赢了m局，其中最长的连胜是k局？（0 < n,m,k < 1e5）

 

题解，

涉及专业领域，术业有专攻，如果有坛友觉得我在**请谅解，我本意是想分享下枯燥的算法竞赛过程中的一些乐子。
如果有坛友对题解感兴趣，这里口胡一下（估计几天后网上也会有正式题解）。
以下作废，看了眼题解最好还是容斥，多项式卷积容易T
胜代表1，负代表0。
首先f(k)为答案，g(k)为最长1串小于等于k的方案数，则f(k) = g(k) - g(k - 1)
考虑这个串有n - m个0，相当于在n-m+1个空中插入p个1串，这p个1串长度和为m。
考虑p个1串长度为m，这个问题的生成函数为 (1 + x + x^2 + ... + x^m)^p，答案是x^m的系数，这部分可以ntt做，答案再乘个组合数，再p从1到m枚举

（CCPC应该是一个程序设计竞赛）

原文标题及地址：

笑死，还真有根据810975出的题
https://keylol.com/t766545-1-1

作者：雪泥灬鸿爪 
(出处: 其乐 Keylol)

试着翻译一下题目描述（因为比较有趣）

在鸭嘴兽王国 (platypus kingdom)，全国上下流行着一款游戏：炉石传说。每局八人，仅有一人能够吃鸡。当第一太难啦，鸭嘴兽们吃了鸡就高兴得不得了，定要在网上大肆宣扬一番才满意。最近，一串神秘的数字“810975”在他们之间传播着。

“810975，新人怎么听不懂？！”

“810975，怎么就你一个听不懂？”

……

Zayin也被新圣经洗脑了，天天在朋友们耳边念叨个不停：在8月10号这一天，鸭嘴兽国王玩了9把吃了7把鸡，其中还有一个5连鸡！这就是810975。今天他又逮到一只新鸭嘴兽Ziyin：“你知道810975吗？不知道是吧，我来告诉你！”然而Ziyin有个问题：“如果我玩了n局赢了m局，其中最长连胜局数为k，那么一共有多少种可能的情况呢？”

（其它的都是问题本身，不好玩就不翻译了）