P1398 数学题3


Problem

http://acm.sjtu.edu.cn/OnlineJudge/problem/1398

题目描述

给定一个数字,他在十进制下从高位到低位一次是n0, n1, n2, n3,…

那么定义它的“差和”为n0-n1+n2-n3+…

如:十进制数字abcdefg,每个字母代表一个位,那么差和为a-b+c-d+e-f+g。

所以十进制数字1234567差和为1-2+3-4+5-6+7=4

现在给你们一个闭区间[m, n],请求出区间内差和为x的数字个数。

输入格式

输入只有一行,三个数字,m n x

30%: 0<= m <= n <=10^3, 50%: 0<= m <= n <=10^8, 100%: 0<= m <= n <=10^18

-100<= x <=100

输出格式

输出只有一个数字,表示区间内差和为x的数字的总和mod1000000007的结果。

Sample Input

100 111 1

Sample Output

211

Analysis

相当捉急的题目。

令F[i][first digit][j]

表示长度为i的数(包括010 这个3位数),第一位为first digit时,差和为j的个数

令g[i][first digit][j]

表示长度为i的数(包括010 这个3位数),第一位为first digit时,差和为j的数之和

之后可以利用简单dp推出f、g

主要难点在于如何把实际的一些数分拆出来。

简化,我们只考虑统计1~n之间满足条件数的和,之后利用减法就能得到区间结果。

(函数calc)这个是不包括有前导0的情况的。

比如说234。我们可以分拆成 0 + [00,99] , 100~199 , 2+[00,34]

如果知道[00,34]有k个数(如何求出这k个数见calcnum)满足我们对这个区间的需求,那么234在2+[00,34]内所有数之和就是[00,34]所有数之和 + 200 *k

然而,我们在去掉头一位时,不可避免地需要统计[00,99]区间内的情况,它是与calc函数不同的。因此我们使用了一个calc2函数来解决这个问题。

取余坑。

Code

    /* **********************************
     * 精简版头文件  修改自岛娘的头文件
     * By lz96@foxmail.com
     * 复制到你的代码头部即可使用
     * **********************************/
    #define T_ long long  //各种循环变量的类型,特殊情况可以改成long long
    #define fuck(s_) {cout<<s_<<endl;return 0;} //输出s_的内容并结束程序:fuck("NO");
    /*************************
     * 各种循环函数
     * re:3个参数:循环变量,起始值,终止值
     * rep: 2个参数:循环变量,终止值/初始值
     * 后缀2/3:二维、三维
     * 后缀0:有则初始值/终止值为0 否则为1
     * 前缀r:有则从大到小循环,否则从小到大循环
     * ***********************/
    #define printarr(a_,x_) rep(i_,x_)cout<<a_[i_]<<" ";cout<<endl; //输出一维数组 输出a[1] ~ a[5] printarr(a,5)
    #define printarr0(a_,x_) rep0(i_,x_)cout<<a_[i_]<<" ";cout<<endl; // 输出a[0] ~ a[4] printarr0(a,5)
    #define printarr2(a_,x_,y_) rep(i_,x_){rep(j_,y_)cout<<a_[i_][j_]<<' ';cout<<endl;} //输出二维数组
    #define printarr20(a_,x_,y_) rep0(i_,x_){rep0(j_,y_)cout<<a[i_][j_]<<' ';cout<<endl;} //输出二维数组,下标从0开始
    #define rep2o(a_,b_,n_) rep(a_,n_) re(b_,a_+1,n_) // for(T_ a_=1;a_<=n_;++a_) for(T_ b_=a_+1;b_<=n_;++b_)
    #define rep20o(a_,b_,n_) rep0(a_,n_) re0(b_,a_+1,n_) // for(T_ a_=0;a_<n_;++a_) for(T_ b_=a_+1;b_<n_;++b_)
    #define rep2(a_,b_,p_,q_) rep(a_,p_) rep(b_,q_)// for(T_ a_=1;a_<=n_;++a_) for(T_ b_=1;b_<=n_;++b_)
    #define rep20(a_,b_,p_,q_) rep0(a_,p_) rep0(b_,q_) // for(T_ a_=0;a_<n_;++a_) for(T_ b_=0;b_<n_;++b_)
    #define rrep2(a_,b_,p_,q_) rrep(a_,p_) rrep(b_,q_)
    #define rrep20(a_,b_,p_,q_) rrep0(a_,p_) rrep0(b_,q_)
    #define rep3(a_,b_,c_,p_,q_,r_) rep(a_,p_) rep(b_,q_) rep(c_,r_)
    #define rep30(a_,b_,c_,p_,q_,r_) rep0(a_,p_) rep0(b_,q_) rep0(c_,r_)
    #define rrep3(a_,b_,c_,p_,q_,r_) rrep(a_,p_) rrep(b_,q_) rrep(c_,r_)
    #define rrep30(a_,b_,c_,p_,q_,r_) rrep0(a_,p_) rrep0(b_,q_) rrep0(c_,r_)
    #define rep(a_,x_) re(a_,1,x_) //rep(i,5)   == for(T_ i=1;i<=5;++i)
    #define rep0(a_,x_) re0(a_,0,x_) //rep0(i,5)   == for(T_ i=0;i<5;++i)
    #define rrep(a_,x_) rre(a_,x_,1) //rrep(i,5)  ==  for(T_ i=5;i>=1;--i)
    #define rrep0(a_,x_) rre(a_,x_-1,0) //rrep0(i,5)  ==  for(T_ i=4;i>=0;--i)
    #define re(a_,s_,t_) for(T_ a_=s_;a_<=t_;++a_) // re(i,2,4)  ==   for(T_ i=2;i<=4;++i)
    #define re0(a_,s_,t_) for(T_ a_=s_;a_<t_;++a_) // re0(i,2,4)  ==   for(T_ i=2;i<4;++i)
    #define rre(a_,s_,t_) for(T_ a_=s_;a_>=t_;--a_)
    #define rre0(a_,s_,t_) for(T_ a_=s_;a_>t_;--a_)
    #define repit(a_,c_) for(__typeof__(a_.begin()) c_=a_.begin();c_!=a_.end();++c_) // 只在GCC上可用:repit(容器,迭代器)
    #define nosync std::ios::sync_with_stdio(false);std::cin.tie(0);ios_base::sync_with_stdio(0) //加在main的第一行,加快输入输出,但之后不能用scanf/printf
    #define DE false //是否在调试模式?
    #define de(s_) if(DE){s_ } //  de(仅仅想在调试时执行的语句)     de(cout<<n<<m<<endl;)
    #include <iostream>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <string>
    #include <cmath>
    #include <algorithm>
    #include <map>
    #include <vector>
    #include <deque>
    #include <list>
    #include <set>
    #include <numeric>
    #include <bitset>
    #include <fstream>
    #include <iomanip>
    #include <sstream>
    #include <ctime>
    #include <stack>
    #include <queue>
    #pragma GCC optimize("O2")
    using namespace std;
    #define endl '\n'
    const int dx4[] = {-1, 0, 1, 0};
    const int dy4[] = {0, 1, 0, -1};  //十字方向的所有坐标 (basex+dx4[i] , basey+dy4[i])
    const long long modb=1000000007;  //取模的数  ModBase
    const long inf=0x3f3f3f3f;      //很大的整数
    const double oo=1e15;           //很大的实数
    const double eps=1e-8;          //很小的实数,计算几何用
    const double pi=acos(-1.0);     //pi
    template<typename T> void clr(T* a_,int n_=0,size_t s_=-1) {if (s_==-1) s_=sizeof(a_); memset(a_,n_,sizeof(a_[0])*s_); }  // clr(a):将a清空为0     clr(a,0xff)将a每个字节清成0xff      clr(a,0xff,4) 将a[0]~a[3]的每一个字节填成0xff
    template<typename T> T sqr(T a_) { return a_*a_; }  //平方
    template<typename T> T cub(T a_) { return a_*a_*a_; }  //立方
    inline T_ mf(T_ n_) {return ((n_<0)?n_+(modb<<2):n_)%modb; }  //mf(n) = n%modb,加上了负数判断,ModFunction
    template<typename T>T max(T a_,T b_,T c_) { return max(a_,max(b_,c_)); } //三个参数的max
    template<typename T>T min(T a_,T b_,T c_) { return min(a_,min(b_,c_)); } //三个参数的min
    inline int dbcmp(double a_, double b_) { return (fabs(a_-b_)<eps)?0:(a_<b_?-1:1); } //允许误差的cmp,< : -1    == : 0    > : 1
    inline double dbdiv(T_ a_, T_ b_) { return static_cast<double>(a_) / b_; } //实数除 dbdiv(3,5)=0.6
    inline double angle(double x_, double y_) { if (x_==0.0) return y_>0?pi/2:3*pi/2; else { double t_=atan2(y_,x_); return (t_<0.0?t_+pi:t_) + y_<0?pi:0.0; }} //计算(x_,y_)的幅角 [0,2*pi)
    /******************************************************************************************/
    long long f[20][11][202], g[20][11][202];

    long long m,n,x;

    long long l(long long d)
    {
        long long ans=0;
        while (d)
        {
            ++ans;
            d/=10;
        }
        return ans;
    }

    long long tenp(long long d)
    {
        long long ans=1;
        while (d--)
          ans *= 10;
        return ans;
    }

    long long calc2(long long len, long long nn, long long xx);
    long long calcnum(long long,long long nn, long long xx);
    long long calc(long long nn, long long xx)
    {
        //cout<<nn<<" "<<xx<<endl;
        //

        long long an =0;
        if (nn<10)
        {
         rep(i,nn)
         {
          an+= g[1][i][xx];
          an %= modb;
         }
         an %= modb;
         //cout<<"an="<<an<<endl;
         return an;
        }
        long long len = l(nn);
        long long first = nn / tenp(len-1);
        rep0(i, first)
        {
            //cout<<"len="<<len<<" i="<<i<<" xx="<<xx<<"  g=";
            //cout<<g[len][i][xx]<<endl;
            if (i>0)
            an += g[len][i][xx];
            else
            an += calc(tenp(len-1)-1,xx);
            an %= modb;
        }
        //cout<<" temp an="<<an<<endl;
        long long pre = xx-100;
        pre -= first;
        pre = -pre;
        pre += 100;
        long long t = tenp(len-1);
        //cout<<" nn="<<nn<<" t="<<t<<endl;
        long long w = nn%t;
        //cout<<" num="<<calcnum(len-1,w,pre)<<endl;
        an += mf(mf(calcnum(len-1,w,pre)*mf(t))*(first)) + mf(calc2(len-1, w,pre));
        //cout<<nn<<" "<<xx<<" "<<an<<" res"<<endl;
        an = mf(an);
        return an;
    }

    long long calcnum(long long len, long long nn, long long xx)
    {
        //cout<<"calcnum "<<len<<" "<<nn<<" "<<xx<<endl;
        //
        if (len<2)
        {
            long an=0;
            rep0(i,nn+1)
          an+= f[1][i][xx];
            an %= modb;
            return an;
        }
        long long an=0;
        long long first = nn / tenp(len-1);
        rep0(i, first)
        {
            if (i>0)
            an += f[len][i][xx];
            else
              an+= calcnum(len-1,tenp(len-1)-1,200-xx);
            an %= modb;
        }

        long long pre = xx-100;
        pre -= first;
        pre = -pre;
        pre += 100;
        long long t = tenp(len-1);
        long long w = nn%t;
        an += calcnum(len-1, w,pre);
        an %= modb;
        return an;

    }

    long long calc2(long long len, long long nn, long long xx)
    {
        //cout<<"calcnum "<<len<<" "<<nn<<" "<<xx<<endl;
        //
        if (len<2)

        {
            long an=0;
            rep0(i,nn+1)
            {
                an+= g[1][i][xx];
                an = mf(an);
            }
            an = mf(an);
            return an;
        }
        long long an=0;
        long long first = nn / tenp(len-1);
        rep0(i, first)
        {
            if (i>0)
              an += g[len][i][xx];
            else
              an+= calc2(len-1,tenp(len-1)-1,200-xx);
            an = mf(an);
        }

        long long pre = xx-100;
        pre -= first;
        pre = -pre;
        pre += 100;
        long long t = tenp(len-1);
        long long w = nn%t;
        an += mf(mf(first* tenp(len-1)) * mf(calcnum(len-1, w,pre)))+ mf(calc2(len-1,w,pre));
        an = mf(an);
        return an;

    }

    int main()
    {
        cin>>m>>n>>x;
        re(i,0,10)
        {
            f[1][i][i+100] += 1;
            g[1][i][i+100] += i;
        }
        re(l, 2, 18)
            rep0(i,10)
            rep0(j,201)
            {
                long long old = -((j-100)-i) + 100;
                rep0(k,10)
                {
                    g[l][i][j] += mf(mf(f[l-1][k][old] * mf((long long)(tenp(l-1)))) * i + g[l-1][k][old])  ;
                    f[l][i][j] += f[l-1][k][old];
                    f[l][i][j] = mf(f[l][i][j]);

                    g[l][i][j] = mf(g[l][i][j]);

                }
                //cout<<l<<" "<<i<<" "<<j<< " "<<f[l][i][j]<<endl;
            }
        //cout<<calc(111,x+100)<<endl;
        //cout<<calc(100,x+100)<<endl;
        //cout<<calc(99,x+100)<<endl;
        //cout<<g[2][1][1+100]<<endl;
        //cout<<g[2][2][100+1]<<endl;
        //cout<<g[2][3][1+100]<<endl;
        //cout<<"xxx"<<endl;
        //cout<<g[3][0][99]<<endl;
        //cout<<g[2][0][101]<<endl;
        //cout<<g[1][0][99]<<endl;
        //cout<<calc(99,x+100)<<endl;
        //cout<<"Xxx - ---------------------------"<<endl;
        //cout<<calc(n,x+100)<<endl;
        //cout<<"XXX ----------------------------------"<<endl;
        cout<< mf(calc(n,x+100) - calc(m-1,x+100)) <<endl;

    }