题目链接：CF258B

还是继续我的数位DP专题学习


题意：在【1，M】中选择7个数，定义数字中含有4或者7的叫做运气数，如4447有4个，可以累计

现在要求：选择第一个数的运气值要严格大于其他6个数的运气总和


分析：

第一思路：用DP预处理dp【pos】【x】：当前位为pos，运气值为x的数有多少个

但是发现这样做，有一点不好：怎么去比较严格大于这个事呢


需要这样定义：dp【pos】【x】【y】：要求最后的运气值是y！

做过这种类似的题啊！当pos==0的时候比较x和y是否相等就好


然后在注意一个前导0的问题，因为0是符合数位DP的，但是不符合题意，所以这个特殊情况要减掉


剩下的就是根据预处理的值来暴力枚举了，6层的DFS

假设我当前的运气值为x，那么剩下需要选择的6个数的运气值总和最大为x-1，带进去dfs跑就好了


上代码

#include<map>
#include<set>
#include<math.h>
#include<time.h>
#include<iostream>
#include<cstdio>
#include<queue>
#include<stack>
#include<stdio.h>
#include<cstring>
#include<string.h>
#include<algorithm>
#include<cstdlib>
using namespace std;

#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define ll rt<<1
#define rr rt<<1|1
#define LL long long
#define ULL unsigned long long
#define maxn 1050
#define maxnum 1000050
#define eps 1e-6
#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)
#define MOD 1000000007

LL digit[15],sum[15],dp[15][15][15];
LL dfs(int pos,int pre,int sum,bool flag){
	if (pos==0) return pre==sum;
	if (flag&&dp[pos][pre][sum]!=-1) return dp[pos][pre][sum];
	int maxnumber=flag?9:digit[pos];
	LL ans=0;
	for(int i=0;i<=maxnumber;i++)
		ans+=dfs(pos-1,pre+(i==4||i==7),sum,flag||i<maxnumber);
	if (flag) dp[pos][pre][sum]=ans;
	return ans;
}

LL solve(int now,int res){
	LL ans=0;
	if (now==7) return 1;
	for(int i=0;i<=res;i++)
		if (sum[i]){
			sum[i]--;
			ans=(ans+(sum[i]+1)*solve(now+1,res-i))%MOD;
			sum[i]++;
		}
	return ans;
}

LL calc(LL n){
	int len=0;
	LL ans=0;
	while(n){
		digit[++len]=n%10;
		n/=10;
	}
	for(int i=0;i<=len;i++)
		sum[i]=dfs(len,0,i,0);
	sum[0]--;
	for(int i=1;i<=len;i++)
		ans=(ans+sum[i]*solve(1,i-1))%MOD;
	return ans;
}

int main(){
	//input;
	LL m;
	memset(dp,-1,sizeof(dp));
	while(scanf("%I64d",&m)!=EOF)
		printf("%I64d\n",calc(m));
	return 0;
}