[CSP-X2024 山东] 消灭怪兽

Luogu

IDLGB4105

Time1000ms

Memory512MB

DifficultyP2

2024山东CSP-X 小学组

怪兽入侵了地球！为了抵抗入侵，人类设计出了按顺序排列好的 $n$ 件武器，其中第 $i$ 件武器的攻击力为 $a_i$，可以造成 $a_i$ 的伤害。武器已经排列好了，因此不能改变顺序。某件武器可以单独攻击，也可以与相邻的武器进行组合攻击。具体来说，每次你可以把相邻的若干个（可以为 $1$ 个，即不进行组合）连续的武器组合起来进行攻击，则攻击力为这些连续的武器攻击力之和。来自外星的怪兽拥有无敌护盾，不会受到任何伤害。但是人类在交战过程中发现怪兽有个致命的弱点：每次当受到 $k$ 或 $k$ 的倍数的伤害时，怪兽的无敌护盾就能被打破。请你帮助人类求出有多少种组合武器的方案，使得造成的伤害能打破怪兽的无敌护盾。 ## Input 第一行两个正整数 $n, k$ 如题所述；第二行为 $n$ 个正整数，其中第 $i$ 个数 $a_i$ 表示第 $i$ 件武器的攻击力。 ## Output 一行一个整数表示答案。 [samples] ## Note ### 样例解释样例 $1$ 解释： $k=3$，而区间 $[1,2].[1,3],[1,5],[2,4],[3,3],[3,5],[4,5]$ 的区间和均为 $3$ 或 $3$ 的倍数，故一共有 $7$ 种方案。 ### 数据范围对于 $20\%$ 的数据，满足 $1 \leq n,k \leq 100$。对于 $40\%$ 的数据，满足 $1 \leq n,k \leq 10^4,1 \leq a_i \leq k$。对于另外 $10\%$ 的数据，满足 $k=2$。对于另外 $10\%$ 的数据，满足所有的 $a_i$ 均相等。对于 $100\%$ 的数据，满足 $1 \leq n \leq 10^6,2 \leq k \leq 10^6,1 \leq a_i \leq 10^9$。

Samples

Input #1

5 3
1 2 3 4 5

Output #1

Input #2

10 11
1 4 8 10 16 19 21 25 30 43

Output #2

Input #3

6 2
2 2 2 2 2 2

Output #3

API Response (JSON)

{
  "problem": {
    "name": "[CSP-X2024 山东] 消灭怪兽",
    "description": {
      "content": "怪兽入侵了地球！ 为了抵抗入侵，人类设计出了按顺序排列好的 $n$ 件武器，其中第 $i$ 件武器的攻击力为 $a_i$，可以造成 $a_i$ 的伤害。 武器已经排列好了，因此不能改变顺序。某件武器可以单独攻击，也可以与相邻的武器进行组合攻击。具体来说，每次你可以把相邻的若干个（可以为 $1$ 个，即不进行组合）连续的武器组合起来进行攻击，则攻击力为这些连续的武器攻击力之和。 来自外星的怪兽",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB4105"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "怪兽入侵了地球！\n\n为了抵抗入侵，人类设计出了按顺序排列好的 $n$ 件武器，其中第 $i$ 件武器的攻击力为 $a_i$，可以造成 $a_i$ 的伤害。\n\n武器已经排列好了，因此不能改变顺序。某件武器可以单独攻击，也可以与相邻的武器进行组合攻击。具体来说，每次你可以把相邻的若干个（可以为 $1$ 个，即不进行组合）连续的武器组合起来进行攻击，则攻击力为这些连续的武器攻击力之和。\n\n来自外星的怪兽...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments