[洛谷U22157]刷水题（数位dp）（hash）

题目背景

做正经题是不可能做正经题的，这辈子都不可能做正经题的，毒瘤题又不会做毒瘤题，就是水题这种东西，才维持了蒟蒻的信心；

题目描述

这里有N+1 道水题，编号分别为0 ~N+1 ,每道水题都有它自己水的程度，具体为对应编号的每位上的数字的乘积，现在为了能够更好的刷水题，我们需要统计一点小东西，统计给出L,R,A,B四个值，具体统计的内容为编号在LL 到RR 这段区间中水的程度在A 到B 之间的水题的编号和，现在请你编写一个程序来完成这个统计并A掉这道水题，因为结果可能很大，请输出在对P 取模意义下答案;

输入输出格式

输入格式：

第一行两个整数N，P ，接下来一行四个数L,R,A,B 表示一次询问；

输出格式：

一个整数表示统计的结果；

输入输出样例

输入样例#1：

输出样例#1：

说明

0<=N,A,B<=1e18,1<=L<=R<=N,2<= P <= 1e9 +7

%20数据满足A = 0

另外%80数据满足A > 0。

因为是出现过的题，但是我把它的询问方式加强了，所以我就不出部分分了。

分析：

详情见scoi2012blinker的仰慕者，对于那道题询问来说是对于定值k的统计结果，这道题询问的是A - B的统计结果。

但我们发现对于所有数可能的水的程度只可能有40000多种，因为质因子只有2,3,5,7

所以hash一遍后，挨个挨个暴力计算即可

对于N这个数我都设为1e18了，233

AC代码：

# include <iostream>

# include <cstdio>

# include <map>

# include <cstring>

# include <algorithm>

using namespace std;

const int M = ;

const int N = ;

typedef long long LL;

LL mod;

LL L,R,P,state[N],sum[][N],num[][N],p[],c[],K,a[],b[],A,B;int tot,hs[M],z;

void insert(LL x)

{

    int k = x % M;

    while(hs[k])

    {

        ++k;

        if(k >= M)k = ;

    }

    hs[k] = ++tot;state[hs[k]] = x;

    if(!x)z = tot;

}

int id(LL x)

{

    int k = x % M;

    while(hs[k])

    {

        if(state[hs[k]] == x)return hs[k];

        ++k;if(k >= M)k = ;

    }

    return ;

}

void init()

{

    p[] = ;

    for(int i = ;i <= ;i++)p[i] = p[i - ] * 10LL % mod;

    for(int i = ;i <= ;i++)

    {

        insert(i);

        num[][id(i)] = ;sum[][id(i)] = i;

    }

    for(int i = ;i <= ;i++)

    {

        int tmp = tot;

        for(int j = ;j <= tmp;j++)

        {

            LL x = state[j];int v = j,u;

            for(LL k = ;k <= ;k++)

            {

                if(!id(x * k))insert(x * k);

                u = id(x * k);

                (num[i + ][u] +=  num[i][v]) %= mod;

                (sum[i + ][u] += (sum[i][v] + (k * p[i]) % mod * num[i][v]) % mod) %= mod;

            }

        }

    }

    for(int i = ;i <= ;i++)

    {

        for(int j = ;j <= tot;j++)

        {

            a[i] = (a[i] + num[i][j]) % mod;

            b[i] = (b[i] + sum[i][j]) % mod;

        }

    }

}

LL dfs(int t,LL pre,LL now,bool lim,bool first)

{

    if(!t)return now ==  ? pre : ;

    int u = id(now);

    if(!lim && !first)

    {

        return ((pre * num[t][u]) % mod * p[t] % mod + sum[t][u]) % mod;

    }

    int q = lim ? c[t] : 9LL;

    LL res = ;

    for(LL k = ;k <= q;k++)

    {

        if(now % k)continue;

        (res += dfs(t - ,(pre * p[] + k) % mod,now / k,lim && k == q,first && !k)) %= mod;

    }

    if(first)(res += dfs(t - ,pre,now,lim && !q,first)) %= mod;

    return res;

}

LL Dfs(int t,LL pre,bool now,bool lim,bool first)

{

    if(!t)return now ? pre : ;

    if(!lim && !first)

    {

        if(!now)

        return ((pre * num[t][z]) % mod * p[t] % mod + sum[t][z]) % mod;

        return ((pre * a[t]) % mod * p[t] % mod + b[t]) % mod;

    }

    int q = lim ? c[t] : ;

    LL res = ;

    for(LL k = ;k <= q;k++)

    {

        (res += Dfs(t - ,(pre * p[] + k) % mod,now || (!first && !k),lim && k == q,first && !k)) %= mod;

    }

    return res;

}

LL solve(LL r)

{

    int len = ;

    while(r)

    {

        c[++len] = r % p[];

        r /= p[];

    }

    if(!len)c[len = ] = ;

    LL ret = ;

    if(A == )ret += Dfs(len,,false,true,true);

    for(int i = ;i <= tot;i++)if(state[i] >= A && state[i] <= B)

    (ret += dfs(len,,state[i],true,true)) %= mod;

    return ret;

}

int main()

{

  scanf("%lld %lld",&A,&mod);

  init();

  scanf("%lld %lld %lld %lld",&L,&R,&A,&B);

  printf("%lld\n",((solve(R) - solve(L - )) % mod + mod) % mod);

}

巴特西