NOIP模拟赛 8.19 序列划分

· · 题解

评价：dalao的标程没有一丝阳气

思路

暴力：一开始碰到题目的时候，我们会先考虑对前一次划分添加一个状态situation，表示前一次划分的子段能否可以被整除，来转移后面的切分状态，这样的时间复杂度是 O(n^2)。

部分代码：

long long di(long long l,long long situ)
{
    if(l==ss.size()) return 0;
    if(dii[l][situ]!=0) return dii[l][situ]-1;
    long long yu=0,sum=0;
    if(situ==0) sum++; else sum=(sum1[l]==true);
    yu=0;
    if(situ==0)
    {
        for(int i=l;i<=ss.size()-1;i++)
         {
            yu=(yu*10+int(ss[i])-48) % mod;
            if(yu==0) sum=(sum+di(i+1,0)) % modd;
                  else sum=(sum+di(i+1,1)) % modd;
         }
    }
    else
    {
        for(int i=l;i<=ss.size()-1;i++)
         {
            yu=(yu*10+int(ss[i])-48) % mod;
            if(yu==0) sum=(sum+di(i+1,0)) % modd;
         }
     } 
     dii[l][situ]=sum% modd +1;
     return sum % modd;
}

这样你只能拿到叁拾分，所以我们接着考虑如何进行优化。我们发现降低时间复杂度的关键是要降低判断某个区间是否能被整除的时间和加快统计同一类型（能否被整除）dp前驱的速度。

对于第一个问题，我们引入一个量来记录整个子段不同后缀被D整除的余数，本质上是希望：

（ x \times 10^n\bmod D=x \bmod D ）

而这个式子在（10，D）=1的时候是成立的，若(10,D) \ne 1，则还需要将D的2,5因子单独提出进行判断。

对于第二个问题，我们可以用一个桶来维护（大小为D）。

最后注意在统计答案时的一些取模细节即可。（反正很阴间）

代码

#include <bits/stdc++.h>
using namespace std;
const long long modd=1e9+7;
int main() 
{
//  freopen("division.in", "r", stdin);
//  freopen("division.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    int d;
    cin >> s >> d;
    int e = 1;
    while (d % 2 == 0) 
    {
        d /= 2;
        e *= 2;
    }
    while (d % 5 == 0) 
    {
        d /= 5;
        e *= 5;
    }
    int n = s.size();
    vector<int> a(n + 1);
    for (int i = 0; i < n; ++i) 
    {
        a[i + 1] = (a[i] * 10 + (s[i] - '0')) % (d * e);
    }
    vector<int> pw(n + 2);
    pw[n+1]=1;
    for(int i=n;i>=1;i--) pw[i]=pw[i+1]*10%d;
    vector<int> base(20);
    base[0] = 1;
    for (int i = 0; i + 1 < 20; ++i) 
    {
        base[i + 1] = base[i] * 10 % (d * e);
    }
    vector<long long> foo(n + 1), bar(n + 1);
    vector<long long> offset_foo(d), offset_bar(d);
    bar[0] = 1;
    long long pref = 0;
    for (int i = 0; i <= n; ++i) 
    {
        foo[i] += pref;
        foo[i]=foo[i]%modd;
        if(foo[i]<0) foo[i]+=modd;
        if (a[i] % e == 0) {
            foo[i] += offset_foo[(long long) a[i] * pw[i] % d];
            foo[i]=foo[i]%modd;
            if(foo[i]<0) foo[i]+=modd;
            bar[i] += offset_bar[(long long) a[i] * pw[i] % d];
            bar[i]%=modd;
            if(bar[i]<0) bar[i]+=modd;
        }
        pref += bar[i];
        pref%=modd; 
        if(pref<0) pref+=modd;

        offset_foo[(long long) a[i] * pw[i] % d] -= bar[i];
        offset_foo[(long long) a[i] * pw[i] % d] %=modd;
         if(offset_foo[(long long) a[i] * pw[i] % d]<0) 
           offset_foo[(long long) a[i] * pw[i] % d]+=modd;
        offset_bar[(long long) a[i] * pw[i] % d] += foo[i] + bar[i];
        offset_bar[(long long) a[i] * pw[i] % d]%=modd;
         if(offset_bar[(long long) a[i] * pw[i] % d]<0) 
           offset_bar[(long long) a[i] * pw[i] % d]+=modd;
        for (int j = i + 1; j <= n && j < i + 20; ++j) 
        {
            if ((a[j] - (long long) a[i] * base[j - i]) % (d * e) == 0) 
            {
                foo[j] -= bar[i];
                foo[j]%= modd; 
                if(foo[j]<0) foo[j]+=modd;
                bar[j] += foo[i] + bar[i];
                bar[j] %=modd;
                if(bar[j]<0) bar[j]+=modd;
            }
            if (a[j] % e == 0 && (long long) a[i] * pw[i] % d == (long long) a[j] * pw[j] % d) 
            {
                foo[j] += bar[i];
                foo[j]%= modd; 
                if(foo[j]<0) foo[j]+=modd;
                bar[j] -= foo[i] + bar[i];
                bar[j] %=modd;
                if(bar[j]<0) bar[j]+=modd;
            }
        }
    }
    cout << (foo[n] + bar[n]) %modd<< "\n";
}