[GESP样题 六级] 亲朋数

Luogu
IDLGP10262
Time2000ms
Memory512MB
DifficultyP3
动态规划 DPGESP
给定一串长度为 $L$、由数字 $0\sim 9$ 组成的数字串 $S$。容易知道,它的连续子串共有 $\frac{L(L + 1)}2$ 个。如果某个子串对应的数(允许有前导零)是 $p$ 的倍数,则称该子串为数字串 $S$ 对于 $p$ 的亲朋数。 例如,数字串 $S$ 为“ $12342$ ”、$p$ 为 $2$,则在 $15$ 个连续子串中,亲朋数有“ $12$ ”、“ $1234$ ”、“ $12342$ ”、“ $2$ ”、“ $234$ ”、“ $2342$ ”、“ $34$ ”、“ $342$ ”、“ $4$ ”、“ $42$ ”、“ $2$ ”共 $11$ 个。注意其中“ $2$ ”出现了 $2$ 次,但由于其在 $S$ 中的位置不同,记为不同的亲朋数。 现在,告诉你数字串 $S$ 和正整数 $p$ ,你能计算出有多少个亲朋数吗? ## Input 输入的第一行,包含一个正整数 $p$。约定 $2 \leq p \leq 128$。 输入的第二行,包含一个长为 $L$ 的数字串 $S$。约定 $1 \leq L \leq 10^6$。 ## Output 输出一行一个整数表示答案。 [samples] ## Background 对应的选择、判断题:<https://ti.luogu.com.cn/problemset/1106> ## Note ## 样例 1 解释 $5$ 个亲朋数,分别 $10$、$102$、$0$、$02$、$2$。
Samples
Input #1
2
102
Output #1
5
Input #2
2
12342
Output #2
11
API Response (JSON)
{
  "problem": {
    "name": "[GESP样题 六级] 亲朋数",
    "description": {
      "content": " 给定一串长度为 $L$、由数字 $0\\sim 9$ 组成的数字串 $S$。容易知道,它的连续子串共有 $\\frac{L(L + 1)}2$ 个。如果某个子串对应的数(允许有前导零)是 $p$ 的倍数,则称该子串为数字串 $S$ 对于 $p$ 的亲朋数。 例如,数字串 $S$ 为“ $12342$ ”、$p$ 为 $2$,则在 $15$ 个连续子串中,亲朋数有“ $12$ ”、“ $1234$ ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10262"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一串长度为 $L$、由数字 $0\\sim 9$ 组成的数字串 $S$。容易知道,它的连续子串共有 $\\frac{L(L + 1)}2$ 个。如果某个子串对应的数(允许有前导零)是 $p$ 的倍数,则称该子串为数字串 $S$ 对于 $p$ 的亲朋数。\n\n例如,数字串 $S$ 为“ $12342$ ”、$p$ 为 $2$,则在 $15$ 个连续子串中,亲朋数有“ $12$ ”、“ $1234$ ”...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments