#560. 「LibreOJ Round #9」Menci 的序列

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: liu_cheng_ao

题目描述

你有一个长为 n 的序列,每个位置是 * 或者 +* 表示让变量加上自身,+ 表示让变量 +1

现在你要选出它的一个子序列(子序列即原序列中取出一些位置,顺序不变地拼成的序列),使得一个初始为 0 的变量在对子序列中的字符依次执行对应操作后 2^k 取模所得结果尽可能大。求出最大可能的结果。

输入格式

第一行两个正整数 n,k ,表示序列长度以及模数为 2^k

第二行一个长为 n 的字符串表示序列。

输出格式

一行一个正整数,为答案的二进制表示,不含前导零,但答案为 0 时要输出 0 (而不是空串)

样例

样例输入

9 5
++*++***+

样例输出

11001

样例解释

有多种选法可以达到最大,如++*++**++++***+

数据范围与提示

对于所有数据, 1\le n,k\le 10^6

子任务编号 分值 n \leq k\leq 特殊限制
1 15 500 10 -
2 500
3 20 10^5 5\times 10^3
4 10^6 不存在两个相邻的 +
5 30 -