一、题目
点此看题
二、解法
虽然有两个变量，但也可以数位 ，可以容斥，就只用判断上界，但我脑子卡了，把下界塞进去暴力搞（虽然还是 了）
设 为到了第 位，第一个数 第二个数是否顶着上界 压着下界的状态压缩，二进制位上只能选 ， ， ，然后就能转移了。一开始我没有加第二维，就是顶着上界等情况就不记忆化，会 ，因为这道题的原因不完全记忆化效率低下，以后可以两种写法都尝试一下。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int M = 2005;
const int MOD = 1e9+7;
int read()
{int x=0,f=1;char c;while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}return x*f;
}
int T,n,k,a[M],dp[M][M][2];char s[M];
int dfs(int x,int d,int q,int up)
{if(!x) return q;if(!up && dp[x][d][q]!=-1) return dp[x][d][q];int ans=0;for(int i=0;i<=9;i++){if(up && i>a[x]) break;if(i==4 || i==7)ans=(ans+dfs(x-1,k,d||q,up&&(i==a[x])))%MOD;elseans=(ans+dfs(x-1,max(d-1,0),q,up&&(i==a[x])))%MOD;}if(!up) dp[x][d][q]=ans;return ans;
}
int work()
{scanf("%s",s);n=strlen(s);for(int i=0;i<n;i++)a[n-i]=s[i]-'0';return dfs(n,0,0,1);
}
int check()
{int last=2000;for(int i=n;i>=1;i--){if(a[i]==4 || a[i]==7){if(last-i<=k) return 1;last=i;}}return 0;
}
signed main()
{memset(dp,-1,sizeof dp);T=read();k=read();while(T--){int l=work()-check(),r=work();printf("%d\n",(r-l+MOD)%MOD);}
}