[SCOI2013]数数

输入包含三行。
第一行仅有一个数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。

C++11(clang++ 3.9) 解法, 执行用时: 37ms, 内存消耗: 5852K, 提交时间: 2019-05-16 20:21:25

#include<iostream>
#include<cstring>
#include<cstdio>
#define ll long long
#define int long long
using namespace std;
const int M=1e5+111;
const ll mod=20130427;
char buf[1<<21],*p1=buf,*p2=buf;
inline int read(){
    int x=0,f=1; char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f;
}
ll B,len,ans,d[M],f[M]={1},sum[M]={1},pre[M],sub[M],dp[M][2];
inline void prep(){ //预处理
        for(int i=1,j;i<=1e5;++i)
                f[i]=f[i-1]*B%mod,
                sum[i]=(sum[i-1]+f[i])%mod; }
inline ll solv(){
    ll ans=pre[len+1]=0; //恶心的pre初始化，最后的坑
    for(int i=1;i<=len;++i) sub[i]=(d[i]*f[i-1]%mod+sub[i-1])%mod;
    for(int i=len;i>=1;--i) pre[i]=(pre[i+1]*B%mod+d[i])%mod;
        //前缀值、后缀值的预处理
    for(int i=1;i<=len;++i){ //dp 转移，查了半天发现没毛病
        dp[i][0]=(dp[i-1][0]*B%mod+B*(B-1)/2%mod*f[i-1]%mod*sum[i-1]%mod)%mod;
        dp[i][1]=(dp[i-1][0]*d[i]%mod+d[i]*(d[i]-1)/2%mod*f[i-1]%mod*sum[i-1]%mod)%mod;
        dp[i][1]=(dp[i][1]+dp[i-1][1]+d[i]*(sub[i-1]+1)%mod*sum[i-1]%mod)%mod;
        ans=(ans+max(0ll,pre[i+1]-1)*dp[i][0]%mod+dp[i][1])%mod;
    } return ans;
}
signed main(){
    B=read(),len=read(),prep();
    for(int i=len;i;--i) d[i]=read();
    for(int i=1;i<=len;++i) //繁杂的数字处理，坑
        if(d[i]){ --d[i]; break; }
        else d[i]=B-1;
    if(!d[len]) --len;
    ans=-solv(), len=read();
    for(int i=len;i;--i) d[i]=read();
    ans+=solv(),printf("%lld\n",(ans%mod+mod)%mod); return 0;
}

详情