2019牛客暑期多校训练营（第四场）K-number

题意：给你一个字符串s，求出其中能整除300的子串个数（子串要求是连续的，允许前面有0）

思路：

》动态规划

记f[i][j]为右端点为i，满足mod 300 = j的子串个数，可以容易的转移

则状态转移方程为：f[i][(10*j+num[i]) %300] = f[i][(10*j+num[i]) %300] + f[i-1][j]

解释：假如给你个数3，很容易得出3mod300的值就是3，f[3] = 1，然后在3后面加一位1，变为31，则31mod300的值为31，f[31] = 1。我们令(10*j+num[i]) mod 300为x，仔细想一想后，你会发现当前f[x]的值可以由现在的f[x]加上之前f[j]的值更新得到，记得最后让f[num[i]]的值加1

题目求的是mod 300 = 0的字串个数，因此，每次让ans的值加上f[i][0]更新就好了

Code

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

const int maxn = 1e5+200;
char s[maxn];
long long dp[maxn][300];

int main()
{
    cin >> s;
    int len = strlen(s);
    long long ans = 0;
    for(int i = 0 ;i < len; i++){
        dp[i][s[i]-'0']++;
        for(int j = 0; j < 300; j++){
            dp[i+1][(j*10+s[i+1]-'0')%300] += dp[i][j];
        }
        ans += dp[i][0];
    }
    cout << ans << endl;
    return 0;
}

View Code

》思维

仔细观察我们可以发现300的倍数既是3的倍数也是100的倍数，那我们只需要满足这个数最后两位是0，前面的和能整除3就好了。

这时我们考虑用前缀和+同模做差，

　　比如，有a b c d e，(a+b)%mod = k，(a+b+c+d+e)%mod也 = k,那么(c+d+e)%mod = 0，即该子序列是mod的整数倍数。

记sum(i)为前i位的和mod 3的值，那么对于长度大于等于2的区间[l，r]，合法条件即为sum(l-1) = sum(r)，且s[r-1]，s[r]为' 0 '

从小到到大枚举r，并同时用cnt这个数组记录有多少个0<=x<=r-2，分别满足sum(x) = 0, 1, 2，

注意会出现sum(i)本身就mod 3为0的情况，这里需要初始化cnt[0] = 1

Code

#include<cstdio>
char s[100005];
long long cnt[5];
int main()
{
    scanf("%s",s);
    cnt[0]=1;
    long long ans = 0;
    int mo = 0;  
    for(int i=0;s[i]!='';i++){
        if(s[i]=='0') ans++;
        if(s[i]=='0'&&s[i+1]=='0')
            ans += cnt[mo];
        mo = (mo+s[i]-'0')%3;
        cnt[mo]++;
    }
    printf("%lld
",ans);
}

View Code

Over~ ~ ~

参考自：https://blog.csdn.net/cacyth/article/details/50623617