bzoj2505: tickets

Description

         有一位售票员给乘客售票，对于每位乘客，他会卖出多张连续的票，直到已卖出的编号的所有位置上的数的和不小于给定的正数k。然后他会按照相同的规则给下一位乘客售票。初始时，售票员持有的编号是从L到R的连续整数。请你求出，售票员可以售票给多少位乘客。

Input

         三个整数L,R,k。

Output

         一个正整数，表示能够拿到票的乘客数。

f[a][b][c]表示开头的和为b，末尾在[0,10)的数，前面补上和为c的一段数字，能分出的段数和剩余的和

预处理a=0..19，b=0..190，c=0..k-1的答案

然后类似zkw线段树查出区间[l,r]对应的信息，合并答案

#include<cstdio>

typedef long long i64;

i64 l,r,p10[];

struct state{

    i64 c;

    int r;

    void operator+=(state w){

        c+=w.c;

        r=w.r;

    }

}f[][][];

struct pos{

    int a,b;

}stk1[],stk2[];

int stp1=,stp2=;

int p1=,p2=;

int k,sl[],pl=,sr[],pr=;

int main(){

    scanf("%lld%lld%d",&l,&r,&k);

    p10[]=;

    for(int i=;i<=;++i)p10[i]=p10[i-]*;

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

        for(int a=;a<k;++a){

            f[][j][a]=(state){a+j>=k,a+j>=k?:a+j};

        }

    }

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

        for(int j=;j<=-i*;++j){

            for(int a=;a<k;++a){

                state&w=f[i][j][a]=f[i-][j][a];

                for(int b=;b<;++b){

                    w+=f[i-][j+b][w.r];

                }

            }

        }

    }

    --l;++r;

    while(l)sl[++pl]=l%,l/=;

    while(r)sr[++pr]=r%,r/=;

    pl=pr;

    int eq=pr;

    while(sl[eq]==sr[eq])--eq;

    int cl=,cr=;

    for(int i=;i<=pr;++i)cl+=sl[i],cr+=sr[i];

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

        cl-=sl[i],cr-=sr[i];

        for(int a=sl[i]+;a<=;++a)stk1[stp1++]=(pos){i-,cl+a};

        for(int a=sr[i]-;a>=;--a)stk2[stp2++]=(pos){i-,cr+a};

    }

    cr-=sr[eq];

    for(int a=sl[eq]+;a<sr[eq];++a)stk1[stp1++]=(pos){eq-,cr+a};

    while(stp2)stk1[stp1++]=stk2[--stp2];

    state w=(state){,};

    for(int i=;i<stp1;++i)w+=f[stk1[i].a][stk1[i].b][w.r];

    printf("%lld\n",w.c);

    return ;

}