Link:
Solution:
明显是一道数位$dp$的题目,就是递推式复杂了点
先要求出一个数$\bar{n}$向添加一位后的$\bar{np}$的转化关系
令$res[\bar{n}]$为数$n$的权值和,
则$res[\bar{np}]=res[\bar{n}]+\sum_{i=1}^{len(n)} \bar{n[i...len(n)]p}$
令$suf[\bar{n}]$为数$n$的后缀和,
则$res[\bar{np}]=res[\bar{n}]+suf[\bar{np}]$
同时$suf$自己的递推式为:$suf[\bar{np}]=base*suf[\bar{n}]+(len(n)+1)*p$
再令$dgt[\bar{n}]$为数$n$的位数,
则$dgt[\bar{np}]=dgt[\bar{n}]+1$
上面的递推式虽然都只针对某一个数$n$,但完全可以逐层推广到之前所有数的和
使原来的$res,suf,dgt$分别表示$\sum res,\sum suf,\sum dgt$,$a$表示数的个数
再用第二维的$0/1$表示是否达到上界,算是数位$dp$的常规套路
剩下的递归式还是看代码吧……
Code:
#include <bits/stdc++.h> using namespace std;
typedef long long ll;
const int MAXN=1e5+,MOD=; int B,l1,l2,dat1[MAXN],dat2[MAXN];
ll pre[MAXN],res[MAXN][],a[MAXN][],suf[MAXN][],dgt[MAXN][]; ll solve(int *dat,int l)
{
memset(res,,sizeof(res));memset(dgt,,sizeof(dgt));
memset(a,,sizeof(a));memset(suf,,sizeof(suf)); a[l+][]=;
for(int i=l;i;i--)
{
int cur=(i==l)?:B; a[i][]=a[i+][];
a[i][]=((cur-)+a[i+][]*B+a[i+][]*dat[i])%MOD;
dgt[i][]=(dgt[i+][]+a[i+][])%MOD;
dgt[i][]=((cur-)+(dgt[i+][]+a[i+][])*B%MOD+(dgt[i+][]+a[i+][])*dat[i]%MOD)%MOD;
suf[i][]=(suf[i+][]*B+dgt[i][]*dat[i])%MOD;
suf[i][]=(pre[cur]+(suf[i+][]*B%MOD*B%MOD+(dgt[i+][]+a[i+][])*pre[B]%MOD)+
(suf[i+][]*B*dat[i]%MOD+dgt[i][]*pre[dat[i]]%MOD))%MOD;
res[i][]=(res[i+][]+suf[i][])%MOD;
res[i][]=(res[i+][]*dat[i]%MOD+res[i+][]*B%MOD+suf[i][])%MOD;
}
return (res[][]+res[][])%MOD;
} int main()
{
scanf("%d",&B);
for(int i=;i<=B;i++) pre[i]=(pre[i-]+i-)%MOD; scanf("%d",&l1);
for(int i=l1;i>=;i--) scanf("%d",&dat1[i]);
scanf("%d",&l2);
for(int i=l2;i>=;i--) scanf("%d",&dat2[i]); for(int i=;i<=l1;i++)
if(dat1[i]){dat1[i]--;break;}
else dat1[i]=B-;
if(!dat1[l1]) l1--; printf("%lld",(solve(dat2,l2)-solve(dat1,l1)+MOD)%MOD);
return ;
}