琼玉牌 (qiongyu)
题目描述
青雀正在玩「帝垣琼玉」牌。
「帝垣琼玉」牌有 \(3\) 种不同花色的琼玉牌，青雀的桌子上有 \(4\) 个放牌的位置，最开始青雀的牌桌上没有琼玉牌。
青雀会进行 \(n\) 回合的抽牌。每个回合开始时，青雀会从牌堆里立即随机抽取 \(2\) 次牌 (牌堆里每种牌都有无穷多张，每次抽上来三种牌的概率相同，同一回合抽上来的两张牌花色可能一样) 。但青雀最多持有 \(4\) 张牌，如果青雀当前持有的牌数大于 \(4\) ,青雀就需要弃掉一些牌，使得牌桌上的牌恰好剩余 \(4\) 张。
青雀十分聪明，会采取当前最优的策略来弃牌。假设弃牌后三种牌的剩余数量分别为 \(A,B,C\) ，那么在所有弃牌方案中，青雀会选择：
1.\(A,B,C\) 中的最大值尽可能大。
2.在满足第一条的基础上，\(A,B,C\) 的次大值尽可能大。
的一种弃牌方案。如果此时有多种弃牌后的方案都满足这个条件，则青雀会选择任意一种。
例如，假设一次摸牌后三种牌剩余数量为 \(\{2,1,3\}\)，那么弃牌后青雀剩余的三种牌数为 \(\{1,0,3\}\) .
摸牌并弃完牌后，若青雀持有的琼玉牌数为 \(4\) 且花色全部相同，那么青雀就会消耗掉自己所有的琼玉牌，并触发一次【暗杠】，此时牌桌上剩余的牌数变为 \(0\).
现在，青雀希望你帮她算出，她摸 \(n\) 回合牌，期望会触发多少次【暗杠】。青雀觉得过大的数字很麻烦，所以你只需要告诉她答案模 \(998244353\) 后的结果即可。
输入格式
一行，输入一个整数 \(n\) ,表示青雀摸牌的回合数。
输出格式
一行，输出一个整数，表示青雀期望触发【暗杠】的次数。
答案对 \(998244353\) 取模。
样例 #1
样例输入 #1
2样例输出 #1
480636170样例 #2
样例输入 #2
3样例输出 #2
460096163样例 #3
样例输入 #3
4样例输出 #3
760436714提示
样例 \(1\) 解释：
青雀两回合摸牌的可能性有 \(3^4\) 种，其中有 \(3\) 种能使青雀摸触发一次【暗杠】，所以期望次数为 \(\frac{1}{27}\).
数据范围：
对于 \(20\%\) 的数据，满足 \(n \le 6\).
对于 \(40\%\) 的数据，满足 \(n \le 1000\).
对于 \(60\%\) 的数据，满足 \(n \le 10^6\).
对于 \(80\%\) 的数据，满足 \(n \le 10^{18}\).
对于 \(100\%\) 的数据，满足 \(1 \le n \le 10^{100000}\).
出题人：比较套路的题
赛时以为剪出转移到每种状态的 DAG ， 建成邻接矩阵的形式，跑其快速幂可以求出走恰好 \(K\) 步时的概率记作 \(P_K\) 。然后 dp ： \(dp_{i}\) 表示前 \(i\) 轮期望，转移显然。卷积形式 FFT 优化能拿 60pts
正解：非常简单，考虑期望 = 所有暗杠次数 除以 总方案数。设 \(dp_{i,j,k,l}\) 表示前 \(i\) 轮状态为 \(\{j,k,l\}\) 的总暗杠次数。发现后三个状态只有 6 种可能，故直接暴力 dp 可以拿 60
优化即为矩阵快速幂。对于 100pts 不用写快速幂，只需要按照 10 进制 dp 即可
复杂度 \(O( \log_{10} n )\)
山东省实验中学 2023 秋提高级友好学校赛前联测 3