卡牌游戏
题目描述
小明正在尝试一种新的牌游戏。游戏规则如下:首先,小明拿到一张写有数字 m 的牌。然后,他会拿到另外 n 张牌,上面分别写有不同的数字,牌排成一排。小明的目标是从这排牌中找到一串连续的牌,这些牌上数字的总和可以被 m 整除。你的任务是判断小明是否可以完成这个目标。
输入描述
第一行包含两个整数:n 和 m。其中 n 是小明拿到的牌的数量(不包括写有 m 的牌),m 是写在第一张牌上的数字。
第二行包含 n 个整数,这些整数分别是 n 张牌上的数字。
输出描述
如果小明可以找到一个连续的牌串,这些牌上数字的和可以被 m 整除,输出'1'。如果找不到符合条件的牌串,输出'0'。
示例 1
输入
6 7
2 12 6 3 5 5
输出
1
示例 2
输入
10 11
1 1 1 1 1 1 1 1 1 1
输出
0
解题思路
核心思想
本题要求判断是否存在连续的牌串,其数字之和能被 m 整除。这是一个经典的同余前缀和问题。
- 前缀和:
- 设数组为 A,前缀和 S[i] = A[0] + A[1] + ... + A[i-1]


