昨天省选班的题。
居然能独立过 2800，震撼，震撼（
考虑使用类似数位 DP 的最后一步统计答案的方法。u1s1 有些人认为这个统计答案的方法才是数位 DP 的精髓，我不知道，我认为 DP 应该是 DP。
先将问题转化为前缀和。然后我们先算出当前 (n) 位的最大的 (leq r) 的 lucky number。
根据数位 DP 的统计答案方法，我们先将 (n-1) 位及以下对答案的贡献先累上去，这个显然是可以预处理的（注意各个位数之间是有衔接部分的，即 (x-1) 个 (7) 和 (x) 个 (4) 的乘积，这个需要计算一下，包括下面所有的衔接部分也是，具体如何计算这个显然可以预处理 (i) 个 (4/7) 的值常数算）。然后就考虑计算 (n) 位的贡献。
我们一位一位地看，每次考虑前缀与当前前缀相等，并且当前位小于当前位的所有 lucky number 的贡献。那么显然它们构成的集合大小为 (2) 的整次幂，其实就是规模小一点的所有 lucky number 前面都戴个前缀帽子。这个规模小一点的贡献我们是已经预处理出来了，于是我们想办法套上去。设帽子为 (head)，那么 ((head+x)(head+y)) 可以用乘法分配律展开，有四项，一项是预处理出来的东西，两项是 (head) 乘以 lucky number 们的和（这个也可以预处理），一项是 (head^2) 乘以一个多少（这个太好算了）。
接下来考虑实现。
- 如何预处理：比较难的两个是 (i) 位 lucky number 总贡献和 (i) 位 lucky number 的和。注意到 (i) 位 lucky number 有 (2^i) 个，其中前 (2^{i-1}) 是 (i-1) 位戴 (4) 帽子，后 (2^{i-1}) 是戴 (7) 帽子。我们可以利用这个来递推。也就很好推了，分配律展开即可，很长的柿子，贡献和需要用到和。然后其他的也就预处理一下 (2) 和 (10) 的幂，多少个 (4/7)。
- 如何算出 (leq r) 的最大 (n) 位 lucky number。我当时写的时候脑子坏掉了，写了个从后往前的 DP，(dp_{i,0/1}) 表示后缀 (i) 第 (i) 位为 (4/7) 是否可行，最后路径还原。其实先判一下 (r) 是否每位都 (geq4)，若否则无，若是则显然每位的取值情况都是独立的，随便 xjb 贪即可。
综上，这题使用了数位 DP 的统计答案方法，但并没有 DP。
复杂度线性。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1000000007;
const int N=100000;
int two[N+1],ten[N+1],four[N+1],seven[N+1],prod[N+1],sum[N+1],Prod[N+1];
void init(){
two[0]=ten[0]=1;
for(int i=1;i<=N;i++)two[i]=2*two[i-1]%mod,ten[i]=10*ten[i-1]%mod;
for(int i=1;i<=N;i++)four[i]=(10*four[i-1]+4)%mod,seven[i]=(10*seven[i-1]+7)%mod;
prod[1]=Prod[1]=28,sum[1]=11;
for(int i=2;i<=N;i++)
prod[i]=(prod[i-1]+4*ten[i-1]%mod*(2*sum[i-1]-four[i-1]-seven[i-1])%mod+4*ten[i-1]%mod*4*ten[i-1]%mod*(two[i-1]-1)+
prod[i-1]+7*ten[i-1]%mod*(2*sum[i-1]-four[i-1]-seven[i-1])%mod+7*ten[i-1]%mod*7*ten[i-1]%mod*(two[i-1]-1)+
(4*ten[i-1]+seven[i-1])%mod*(7*ten[i-1]+four[i-1])%mod)%mod,
sum[i]=(2*sum[i-1]+11*ten[i-1]%mod*two[i-1]%mod)%mod,
Prod[i]=(Prod[i-1]+prod[i]+seven[i-1]*four[i]%mod)%mod;
}
int na,nb;
char a[N+1],b[N+1];
int lar[N+1];
bool dp[N+1][2],pa[N+1][2];
int sol(int n,char s[]){
memset(pa,-1,sizeof(pa));memset(dp,0,sizeof(dp));
if(s[n]>='4')dp[n][0]=true;
if(s[n]>='7')dp[n][1]=true;
for(int i=n-1;i;i--){
if(s[i]>='4'){
if(dp[i+1][1])dp[i][0]=true,pa[i][0]=1;
else if(dp[i+1][0])dp[i][0]=true,pa[i][0]=0;
}
if(s[i]>='7'){
if(dp[i+1][1])dp[i][1]=true,pa[i][1]=1;
else if(dp[i+1][0])dp[i][1]=true,pa[i][1]=0;
}
}
int now=dp[1][1]?1:dp[1][0]?0:-1;
lar[1]=now;
for(int i=1;~now&&i<n;i++){
now=pa[i][now];
lar[i+1]=now;
}
int ans=Prod[n-1];
if(!~now)return ans;
// for(int i=1;i<=n;i++)cout<<lar[i];puts(" hsc 啊可爱哦爱");
now=0;int las=0;
if(n>1)las=seven[n-1];
for(int i=1;i<=n;i++){
int head=(10*now+4)%mod*ten[n-i]%mod;
if(lar[i]==1)(ans+=las*(head+four[n-i])%mod+
prod[n-i]+head*(2*sum[n-i]-four[n-i]-seven[n-i])%mod+head*head%mod*(two[n-i]-1)%mod)%=mod,
las=(head+seven[n-i])%mod;
now=(10*now+(lar[i]==0?4:7))%mod;
}
(ans+=las*now)%=mod;
return ans;
}
signed main(){
init();
// return cin>>a+1,na=strlen(a+1),cout<<sol(na,a)<<"
",0;
cin>>a+1>>b+1;
na=strlen(a+1),nb=strlen(b+1);
cout<<((sol(nb,b)-sol(na,a))%mod+mod)%mod<<"
";
return 0;
}
然后 tzc 还发了个 comment 题解，欢迎去观膜，反正我是 D 了他。