Lutece 2179 子串

题目链接:
https://acm.uestc.edu.cn/problem/zi-chuan/description

题目大意:求子串能被k整除的个数

分析:

这道题是利用余数的性质,大概。

数据过大,所以要使用滚动数组。其实这个2e7开一维也会爆,只是OJ没有MLE而已……感觉正确的做法应该是new或者vector。

利用奇偶的性质来回滚动。

枚举每一个数字,先把这个数字除k的余数加入数组,然后把前面所有遗留下来的余数都算一下。

sum每次加余数为0的情况即可。

一开始把第一个数字%k为0的情况漏了,所以WA了几次。

代码:

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
long long dp[2][20000001];
long long n,k,now,pre,nownum,sum=0;
string str;
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n>>k;
    cin>>str;
    memset(dp,0,sizeof(dp));
    ++dp[0][(str[0] - '0')%k];
    sum+=dp[0][0];
    for(long long i=1;i<n;++i)
    {
        now=i%2;pre=(i+1)%2;
        nownum=str[i] - '0';
        ++dp[now][nownum%k];
        for(long long j=0;j<k;++j)
        {
            dp[now][(j*10+nownum)%k]+=dp[pre][j];
            dp[pre][j]=0;
        }
        sum+=dp[now][0];
    }
    cout<<sum<<endl;
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注