[中山市赛 2024/科大国创杯小学组 2023] 倍数子串/子串

Luogu
IDLGB4185
Time1000ms
Memory512MB
DifficultyP2
递推20232024数论安徽广东排列组合科创活动小学活动科大国创杯
Jimmy 对数字有着异于常人的热爱。有一天,他随便写出来一个数字——$04320$,然后开始对着这个数字写写画画。他发现,从这个数字中随便选出连续的一段(Jimmy 把这个称为连续子串),有可能是 $4$ 的倍数,例如 $4$,$04$,$32$,$432$ 等;也有可能是 $5$ 的倍数,例如 $20$,$320$ 等。 Jimmy 的老师恰好路过此处,他向正沉迷于自己发现的 Jimmy 提了一个有趣的问题——给定一个指定的数字串,请问有多少连续子串是 $4$ 或者 $5$ 的倍数呢? 老师还特别提醒他: * 连续子串的开头可以是 $0$; * 两个连续子串只要是从数字串中的不同位置选出来的,它们就算是不同的; * 如果一个连续子串同时是 $4$ 和 $5$ 的倍数,应当只被计算一次哦! ## Input 一行一个数字串,长度为 $n$。 ## Output 一行一个整数,表示所有的连续子串中,为 $4$ 或者 $5$ 的倍数的数量。 [samples] ## Background 本题题面为 2024 年中山市赛版本,在题面主人公上与 2023 年安徽省科大国创杯小学组略有区别。 ## Note ### 样例解释 1 所有满足题意的连续子串分别为:$0$,$04$,$0432$,$04320$,$4$,$432$,$4320$,$32$,$320$,$20$,$0$。 其中有两个相同的 $0$,这是因为它们是从数字串中的不同位置选出来的(一个在开头处,一个在结尾处)。 ### 数据范围 - 对于 $10\%$ 的数据,保证 $n = 1$。 - 对于 $60\%$ 的数据,保证 $1 \leq n \leq 10^3$。 - 对于 $100\%$ 的数据,保证 $1 \leq n \leq 10^6$。
Samples
Input #1
04320
Output #1
11
Input #2
2000
Output #2
9
API Response (JSON)
{
  "problem": {
    "name": "[中山市赛 2024/科大国创杯小学组 2023] 倍数子串/子串",
    "description": {
      "content": "Jimmy 对数字有着异于常人的热爱。有一天,他随便写出来一个数字——$04320$,然后开始对着这个数字写写画画。他发现,从这个数字中随便选出连续的一段(Jimmy 把这个称为连续子串),有可能是 $4$ 的倍数,例如 $4$,$04$,$32$,$432$ 等;也有可能是 $5$ 的倍数,例如 $20$,$320$ 等。 Jimmy 的老师恰好路过此处,他向正沉迷于自己发现的 Jimmy 提",
      "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": "LGB4185"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Jimmy 对数字有着异于常人的热爱。有一天,他随便写出来一个数字——$04320$,然后开始对着这个数字写写画画。他发现,从这个数字中随便选出连续的一段(Jimmy 把这个称为连续子串),有可能是 $4$ 的倍数,例如 $4$,$04$,$32$,$432$ 等;也有可能是 $5$ 的倍数,例如 $20$,$320$ 等。\n\nJimmy 的老师恰好路过此处,他向正沉迷于自己发现的 Jimmy 提...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments