[CCO 2023] Binaria

Luogu

IDLGP10066

Time1000ms

Memory1024MB

DifficultyP5

2023CCO（加拿大）图论建模

你被廉价通信组织（CCO）雇佣来研究一项突破性的通信技术：子消息和（SMS）。这个革命性的想法是这样的。给定一个长度为 $N$ 的二进制字符串和一个满足 $K \leq N$ 的正整数 $K$，该字符串的 SMS 由 $N-K+1$ 个整数组成。序列中的第一个数是前 $K$ 位的和，第二个数是第 $2$ 位到第 $K+1$ 位的和，依此类推，最后一个数是第 $N-K+1$ 位到第 $N$ 位的和。例如，如果 $K=4$，那么二进制字符串 $110010$ 的 SMS 是 $2,2,1$。这是因为 $1+1+0+0=2,1+0+0+1=2$，以及 $0+0+1+0=1$。由于你是一个新手，你的工作不是从给定的 SMS 中找到原始的二进制字符串，而是找到可能形成这个 SMS 的二进制字符串的数量。 ## Input 第一行包含两个用空格分隔的整数 $N$ 和 $K$。第二行包含 $N-K+1$ 个用空格分隔的整数，保证它至少是一个二进制字符串的 SMS。 ## Output 输出 $T$ 对 $10^{6}+3$ 取模的结果，其中 $T$ 是等于与给定 SMS 对应的可能的二进制字符串的总数的正整数。 [samples] ## Note 长度为 $7$ 的可能的字符串有 $1011001$，$1101010$ 和 $1110011$。对于所有的数据，有 $1\leq N\leq 10^6$，$1 \leq K \leq N$。 | 子任务编号 | 分值 | $N$ 的范围 | $K$ 的范围 | | :-: | :-: | :-: | :-: | |1 |12 |$1 \leq N \leq 10$| $K \leq 3$| |2 |12 | $1 \leq N \leq 10$|无 | |3 |16 |$1 \leq N \leq 1000$ |$K \leq 10$| |4 |16 |$1 \leq N \leq 10^{6}$| $K \leq 20$| |5 |16 | $1 \leq N \leq 10^{6}$| $K\leq 3000$| |6 |28 |$1 \leq N \leq 10^{6}$|无|

Samples

Input #1

7 4
3 2 2 2

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[CCO 2023] Binaria",
    "description": {
      "content": "你被廉价通信组织（CCO）雇佣来研究一项突破性的通信技术：子消息和（SMS）。这个革命性的想法是这样的。 给定一个长度为 $N$ 的二进制字符串和一个满足 $K \\leq N$ 的正整数 $K$，该字符串的 SMS 由 $N-K+1$ 个整数组成。序列中的第一个数是前 $K$ 位的和，第二个数是第 $2$ 位到第 $K+1$ 位的和，依此类推，最后一个数是第 $N-K+1$ 位到第 $N$ 位的",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10066"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "你被廉价通信组织（CCO）雇佣来研究一项突破性的通信技术：子消息和（SMS）。这个革命性的想法是这样的。\n\n给定一个长度为 $N$ 的二进制字符串和一个满足 $K \\leq N$ 的正整数 $K$，该字符串的 SMS 由 $N-K+1$ 个整数组成。序列中的第一个数是前 $K$ 位的和，第二个数是第 $2$ 位到第 $K+1$ 位的和，依此类推，最后一个数是第 $N-K+1$ 位到第 $N$ 位的...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments