{"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来自外星的怪兽拥有无敌护盾，不会受到任何伤害。\n\n但是人类在交战过程中发现怪兽有个致命的弱点：每次当受到 $k$ 或 $k$ 的倍数的伤害时，怪兽的无敌护盾就能被打破。\n\n请你帮助人类求出有多少种组合武器的方案，使得造成的伤害能打破怪兽的无敌护盾。\n\n## Input\n\n第一行两个正整数 $n, k$ 如题所述；\n\n第二行为 $n$ 个正整数，其中第 $i$ 个数 $a_i$ 表示第 $i$ 件武器的攻击力。\n\n## Output\n\n一行一个整数表示答案。\n\n[samples]\n\n## Note\n\n### 样例解释\n\n样例 $1$ 解释：\n\n$k=3$，而区间 $[1,2].[1,3],[1,5],[2,4],[3,3],[3,5],[4,5]$ 的区间和均为 $3$ 或 $3$ 的倍数，故一共有 $7$ 种方案。\n\n### 数据范围\n\n对于 $20\\%$ 的数据，满足 $1 \\leq n,k \\leq 100$。\n\n对于 $40\\%$ 的数据，满足 $1 \\leq n,k \\leq 10^4,1 \\leq a_i \\leq k$。\n\n对于另外 $10\\%$ 的数据，满足 $k=2$。\n\n对于另外 $10\\%$ 的数据，满足所有的 $a_i$ 均相等。\n\n对于 $100\\%$ 的数据，满足 $1 \\leq n \\leq 10^6,2 \\leq k \\leq 10^6,1 \\leq a_i \\leq 10^9$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGB4105","tags":["2024","山东","CSP-X 小学组"],"sample_group":[["5 3\n1 2 3 4 5","7"],["10 11\n1 4 8 10 16 19 21 25 30 43","7"],["6 2\n2 2 2 2 2 2","21"]],"created_at":"2026-03-03 11:09:25"}}