预处理sum数组，sum[i]表示1-m中有i个4或7的数有多少个，这个数位dp很好写
然后就是枚举第七个数含有的4,7数目，dfs剩下的六个数=
1 #include2 #include 3 #include 4 using namespace std; 5 #define LL long long 6 #define MOD 1000000007 7 LL num[15],dp[15][15][15],sum[15]; 8 LL dfs(LL pos,LL pre,LL sum,LL limit) 9 {10 LL ans=0;11 if (pos==0) return pre==sum;12 if (!limit&&dp[pos][pre][sum]!=-1) 13 return dp[pos][pre][sum];14 LL tmp=limit?num[pos]:9,i;15 for (i=0;i<=tmp;i++)16 ans+=dfs(pos-1,pre+(i==4||i==7),sum,limit&&i==tmp);17 if (!limit) dp[pos][pre][sum]=ans;18 return ans;19 }20 LL solve(LL now,LL res)21 {22 LL ans=0,i;23 if (now==7) return 1;24 for (i=0;i<=res;i++)25 if (sum[i]>0)26 {27 sum[i]--;28 ans=(ans+(sum[i]+1)*solve(now+1,res-i))%MOD;29 sum[i]++;30 }31 return ans;32 }33 int main()34 {35 LL m,cnt=0,ans=0,i;36 scanf("%I64d",&m);37 memset(dp,-1,sizeof(dp));38 while (m){39 num[++cnt]=m%10;40 m/=10;41 }42 for (i=0;i<=cnt;i++) sum[i]=dfs(cnt,0,i,1); sum[0]--;43 for (i=1;i<=cnt;i++)44 ans=(ans+sum[i]*solve(1,i-1))%MOD;45 printf("%I64d\n",ans);46 return 0;47 }
题目链接：