#2222. 0418 t2

    ID: 2222 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>TEAM赛事:contest1727来源:qoj.ac数据:公开样例字符串动态规划

0418 t2

0418 t2

题目描述

时间限制:1s 空间限制:512MB 题面描述 你被廉价通信组织雇佣来研究一项突破性的通信技术:子消息和(SMS)。这个革命性的想法是这样 的。 给定一个长度为 的二进制字符串和一个满足 的正整数 ,该字符串的 SMS 由 个整数组成。序列中的第一个数是前 位的和,第二个数是第 位到第 位的和,依此类推,最 后一个数是第 位到第 位的和。 例如,如果 ,那么二进制字符串 的 SMS 是 。这是因为 ,以及 。 由于你是一个新手,你的工作不是从给定的 SMS 中找到原始的二进制字符串,而是找到可能形成这个 SMS 的二进制字符串的数量。 输入格式 第一行包含两个用空格分隔的整数 和 。 第二行包含 个用空格分隔的整数,保证它至少是一个二进制字符串的 SMS。 输出格式 输出 对 取模的结果,其中 是等于与给定 SMS 对应的可能的二进制字符串的总数的正整 数。 样例1输入 1 7 4 2 3 2 2 2 样例1输出 1 3 样例1解释 长度为 的可能的字符串有 和 , 。 数据范围和提示 对于所有的数据,有 , 。 的范围 的范围 子任务编号 分值 无 无

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

7 4
3 2 2 2
3