bzoj3326: [Scoi2013]数数

Description

Fish 是一条生活在海里的鱼，有一天他很无聊，就开始数数玩。

他数数玩的具体规则是：

1. 确定数数的进制B

2. 确定一个数数的区间[L, R]

3. 对于[L, R] 间的每一个数，把该数视为一个字符串，列出该字符串的每一个（连续的）子串对应的B进制数的值。

4. 对所有列出的数求和。

现在Fish 数了一遍数，但是不确定自己的结果是否正确了。由于[L, R] 较大，他没有多余精力去验证是否正确，你能写一个程序来帮他验证吗？

Input

输入包含三行。
第一行仅有一个数B，表示数数的进制。
第二行有N +1 个数，第一个数为N，表示数L 在B 进制下的长度为N，接下里的N个数从高位到低位的表示数L 的具体每一位。
第三行有M+ 1 个数，第一个数为M，表示数R 在B 进制下的长度为M，接下里的M个数从高位到低位的表示数R 的具体每一位。

20% 数据，0 <= R <= L <= 10^5。
50% 数据，2 <= B <= 1000，1 <= N,M <= 1000。
100% 数据，2 <= B <= 10^5，1 <= N,M <= 10^5。

Output

输出仅一行，即按照Fish 数数规则的结果，结果用10 进制表示，由于该数可能很大，输出该数模上20130427的模数。

数位dp

#include<bits/stdc++.h>

typedef unsigned long long u64;

const int P=,N=2e5+;

char buf[],*ptr=buf+;

int G(){

    if(ptr-buf==)fread(ptr=buf,,,stdin);

    return *ptr++;

}

int _(){

    int x=;

    if(ptr-buf<){

        while(*ptr<)++ptr;

        while(*ptr>)x=x*+*ptr++-;

    }else{

        int c=G();

        while(c<)c=G();

        while(c>)x=x*+c-,c=G();

    }

    return x;

}

int fix(int x){return x+(x>>&P);}

struct num{

    int a;

    num(int x=):a(x){}

    num operator+(num x){return fix(a+x.a-P);}

    num operator-(num x){return fix(a-x.a);}

    num operator*(num x){return u64(a)*x.a%P;}

};

num S(num l,num r){

    return (u64(l.a+r.a)*(r.a-l.a+)>>)%P;

}

int B,n,m;

int ns[N],ms[N];

num v0[N],v1[N],pw[N],ps[N],f0[N][],f1[N][];

num cal(int*a,int n){

    num s=,r0=,r1=;

    for(int i=;i<n;++i)s=s+(v1[i-]+v0[i-])*(B-)+S(,B-)*ps[i-]*pw[i-];

    for(int i=n;i;--i){

        int L=(i==n),R=a[i]-;

        if(L<=R){

            num D=R-L+;

            num z0=v0[i-]*D+S(L,R)*ps[i-]*pw[i-];

            num z1=v1[i-]*D+z0;

            s=s+z1+(r1+r0*(ps[i]-))*D*pw[i-]+z0*(n-i);

        }

        r0=r0*B+num(a[i])*(n-i+);

        r1=r1+r0;

    }

    return s;

}

int main(){

    B=_();

    n=_();

    for(int i=n;i;--i)ns[i]=_();

    m=_();

    for(int i=m;i;--i)ms[i]=_();

    ++ms[];

    for(int i=;ms[i]==B;++ms[i+],ms[i]=,++i);

    if(ms[m+])++m;

    ps[]=pw[]=;

    for(int i=;i<=n||i<=m;++i){

        pw[i]=pw[i-]*B;

        ps[i]=ps[i-]+pw[i];

        v0[i]=v0[i-]*B+S(,B-)*ps[i-]*pw[i-];

        v1[i]=v1[i-]*B+v0[i];

    }

    printf("%d\n",(cal(ms,m)-cal(ns,n)).a);

    return ;

}