首页 > CCA的拆分
开通博客写题解
头像 __故人__
发表于 2020-09-15 19:47:08
分析 在比赛中没有做出了，对矩阵的掌握还是太菜了。先对与原问题考虑。我们发现这个问题其实并不好考虑，其中涉及的状态太多，但是考虑一下用全部方案减去不合法的方案来计算。 。先看前面的 。这里有两种理解。 考虑在每个点后面是否划分那么总的方案数为 。 也可以用插板法来理解，那么我们总的方案数为 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 Muscari
发表于 2020-09-05 22:25:55
考虑容斥，即任意拆分的方案数减去拆分成不喜欢的数的方案数。 先考虑前者。设 表示 任意拆分的方案数，则有 即 再考虑后者。考虑 DP，设 为 拆分为不喜欢的数的方案数，则有 因为 ，所以把相邻的 个状态存到矩阵里，然后矩阵快速幂即可。 // ======================== 展开全文
去ta的博客 赞 (3) 回复(1) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”