链接： D. Little Elephant and Elections
题意：
从 1 到 m 选 7 个数，使得其中一个数中 数位4 7 的个数大于其他 6 个数中 数位4 7 的个数的和。
思路：
- 先用数位 dp 求出分别含 0 - 9 个 4 ,7 的数的个数。
- 然后枚举第一个人选的 数中 4 7 的个数，再 dfs 枚举其他 6 个人选的数（ 6 个人的和小于第一个人）。
#include<iostream>
#include<cstdio>
#include<stack>
#include<math.h>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll ;
const int maxn=1e6+7;
const int mod = 1e9 +7;
ll dp[15][15][15][3],a[20],poss,num[maxn],ans,anss,vis[15];
ll dfs(int pos,int sum,int k,int limit,int sta){if(pos==-1) return sum == k && sta == 0;if(!limit&&dp[pos][sum][k][sta]!=-1) return dp[pos][sum][k][sta];int up=limit ? a[pos] : 9;ll tmp=0;for(int i=0; i <= up; i++){tmp += dfs(pos-1,sum + (i == 4 || i == 7),k,limit &&(i == a[pos]),sta && (i == 0));}if(!limit) dp[pos][sum][k][sta]=tmp;return tmp;
}
ll solve(ll x,int k){int pos = 0;while(x > 0){a[pos++] = x % 10;x/=10;}return dfs(pos-1,0,k,1,1);
}
void dfs2(int pos,int sum,int ma,ll x){if(sum >= ma) return ; //剩余 6 个人的 4,7 个数大于第一个人 ,不满足if(pos == 6){anss = (anss + x) % mod;return ;}for(int i = 0; i <= 9; i++){if(num[i] >= 0){num[i] --;dfs2(pos + 1,sum + i, ma, x * (num[i]+1) % mod);num[i] ++;}}
}
int main(){memset(dp,-1,sizeof(dp));ll x;scanf("%lld",&x);for(int i = 0; i <= 9; i ++){num[i] = solve(x,i) % mod; // 有 i 个 4 7 的数的个数}for(int i = 1; i <= 9; i++){ // 枚举第一个人的 4 7 个数anss = 0;dfs2(0,0,i,num[i]); //枚举6个人的 4 7 个数ans = (ans + anss) % mod;}printf ("%lld\n",ans);
}