1 条题解
-
0
10pts
暴力枚举所有可能的情况,进行判定。
30pts
可能满足要求的 至多 种,枚举哪些 满足条件作容斥,把相同的数放在一起,答案为 ,把所有可能的情况的答案加在一起即可。
100pts
我们考虑对于一个 而言,满足要求的字符串有 ,但是答案会算重。
因此我们考虑对于一个 ,计算 是所有满足要求的 中最小的一个时的方案数。
这意味着不存在 ,使得 。
又由于 成立,因此 。
对比两个式子,可以得到 。
即如果 是所有满足要求的 中最少的一个,等价于 是一个不好的字符串,但在这里 ,而原问题中 ,有细微差异。
记 为长度为 的字符串中好的个数(), 为好的个数(),那么有
上述表达式可以利用前缀和进行优化,时间复杂度为 。
$$g[n]=m^n -(\sum_{2i \leq n} g[i] \times m^{-2i}) \times m^n$$
- 1
信息
- ID
- 196
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 5
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者