NOIonline
愤怒的小 N(angry)- CCF NOI Online 能力测试 提高组 2021第一题
【题目描述】
极度愤怒的小 N 通关了一款游戏来泄愤。
这款游戏共有 n 关,分别为第 0 关、第 1 关、第 2 关、···、第 n−1 关。这些关卡中有一些是普通关卡,另一些则是奖励关卡。 这款游戏中普通关卡与奖励关卡的分布比较特殊。如果用字符 a 表示普通关卡,用 字符 b 表示奖励关卡,那么第 0 关、第 1 关、第 2 关、···、第 n−1 关依次排列形成 的字符串是一个无穷字符串 s 的前缀,且 s 可以按照如下方式构造:
- 初始时 s 为包含单个字符 a 的字符串。
- 将 s 的每个字符 a 替换成字符 b,每个字符 b 替换成字符 a 得到字符串 t,然后 将 t 拼接到 s 后。
- 不断执行 2. 得到的字符串就是最终的 s。
可以发现 s = abbabaabbaababba···,所以这款游戏的第 0 关是普通关卡,第 1 关 是奖励关卡,第 2 关是奖励关卡,第 3 关是普通关卡,以此类推。 通过游戏的第 i 关可以得到 f(i) 分,其中 f(x) = a0 + a1x + a2x2 +···+ ak−1xk−1 是一个固定的 k−1 次多项式。 小 N 通关时一气之下通过了所有奖励关卡而忽略了所有普通关卡,然后就把游戏 卸载了。现在回想起来,他想要知道他在卸载游戏前的总得分对 10⁹ + 7 取模后的结果。
【输入格式】 从文件 angry.in 中读入数据。 第一行一个正整数 n,表示游戏的关卡数目。为方便,n 以二进制表示给出。 第二行一个正整数 k,表示多项式的次数加一。 第三行 k 个非负整数,分别为 a0,a1,a2,…,ak−1,表示多项式的各项系数。
【输出格式】 输出到文件 angry.out 中。 一行一个非负整数,表示小 N 卸载游戏前的总得分对 109 + 7 取模后的结果。
【样例 1 输入】
1 1000 2 3 3 3 2 1
【样例 1 输出】
1 110
【样例 1 解释】
这款游戏共有 8 关,通关第 i 关可以得到 (3 + 2i + i2) 分。第 1,2,4,7 关为奖励关, 小 N 通过这几关分别得到了 6,11,27,66 分,共 110 分。
【样例 2 输入】1
2
311111100101
4
2 0 2 1
【样例 2 输出】1
143901603
【样例 3 输入】1
2
31001011001101001
16
1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1
【样例 3 输出】1
184740992
【数据范围与提示】 对于所有测试点:0 ≤log₂n < 5×10⁵,1 ≤ k ≤ 500,0 ≤ ai < 10⁹ + 7,a的第k-1项≠ 0。
我的代码
1 |
|
这里的fastExponentiation其实有更好的方法,但是没从本子那边拿到(我自己也想不出来😥)