题目思路

15的倍数 等价于：这个数既是3的倍数，又是5的倍数. 3的倍数要求数位和是3的倍数,5的倍数要求最后一位是5或者0

所以答案分为两部分，一部分是删最后一段，改变了最后一位，使得剩余部分满足两个条件，另一部分是在最后一位满足条件的前提下删中间的一段

代码

#include <bits/stdc++.h>
using namespace std;

string s;
long long ans;
void solve() {
    int n = s.size();
    int all = 0;			//all是所有数的数位和模3的结果，只有删除的部分也是这个值，就满足剩余的数是3的倍数
    for(char t: s) {
        all += t-'0';
        all %= 3;
    }
    int t = 0;
    for(int i = n-1; i > 0 ; i --) {		//第一部分，枚举，看剩余的部分是否满足条件
        t += s[i]-'0';
        t %= 3;
        if((s[i-1] - '0') % 5 == 0 && t == all) {
            ans++;
        }
    }
    if((s[n-1] - '0') % 5 != 0) return;		//不满足第二部分的前提，直接返回
    int dp[3] = {};			//此时最后一位一定满足条件，只需要考虑数位和为3的倍数即可，用动态规划解决
    for(int i = 0 ; i+1 < n ; i ++) {
        int t[3] = {};
        int now = (s[i] - '0') % 3;
        t[now] ++;
        for(int j = 0 ; j < 3 ; j ++) {
            t[(j+now)%3] += dp[j];
        }
        for(int j = 0 ; j < 3 ; j ++) {
            dp[j] = t[j];
        }
        ans += dp[all];
    }
}
int main()
{
    cin >> s;
    solve();
    cout << ans << endl;
}

题目内容

曾经有一个小镇叫做“数字王国”，这个小镇以数字相关的工艺和技术而闻名于世。其中最出名的数字工匠就是小红。他被认为是数字领域中最聪明的人之一。他的天赋是发现数字之间的规律，并创造一些有趣的数字游戏。

其中一天，小红想出了一个游戏：删除数字。这个游戏的规则是：给定一个正整数，你需要删除其中连续的一段数字，使得它变成15的倍数。他想知道有多少种不同的删除方式可以达到这个目标。

现在，他把这个问题交给了你。

注：删除的位置不同，即可记为两种不同的方式，并且允许删除后的数存在前导零。同时,不能全删也不能不删

输入描述

输入一个正整数 $n$ 。 $1\le n \le 10^{100000}$

输出描述

一个正整数，代表删除的方案数。

样例

输入

12313565

输出

9