#include <cstdio> #include <cstring> #include <cmath> #include <map> #include <algorithm> #include <cstdlib> #define SIZES 40000 #define mod 1000000007ll using namespace std; long long dp[20][20]; long long res[20]; int bit[20],bn; long long m,n,pn,ans; void deep(int now,int _max,int party,long long cur)//now代表拥有的幸运数字的个数,_max上限,party代表序号,cur为方案数 { if (now>_max) return;//已经超过 if (party==7) { if (now<_max){ ans+=cur;//加到答案中 ans%=mod; } return; } for (int i=0;i<bn;i++) { if (res[i])//是否还可行 { res[i]--; deep(now+i,_max,party+1,cur*(res[i]+1)%mod); res[i]++; } } } long long dfs(long long pos,long long target,long long limit)//pos代表处理的位数,target为还需几个幸运数,limit代表目前是否有限制 { long long sum=0; if (pos==0) return target==0;//是否符合要求 if ((limit==0)&&(dp[pos][target]!=-1)) return dp[pos][target];//已经计算过的不必计算 long long tail=limit?bit[pos]:9;//确定枚举的上限 for (int i=0;i<=tail;i++) sum+=dfs(pos-1,target-(i==4||i==7),(limit==1)&&(bit[pos]==i)); if (limit==0) dp[pos][target]=sum; return sum; } void cal(long long x) { ans=bn=0; long long y=x; while (y) { ++bn; bit[bn]=y%10; y/=10; } for (int i=0;i<=bn;i++) res[i]=dfs(bn,i,1);//记忆化搜索算出可选个数 res[0]-=1;//去掉单个数字为0的情况 for (int i=1;i<=bn;i++) deep(0,i,1,res[i]);//枚举所选的幸运数字个数 } int main() { long long m; memset(dp,-1,sizeof dp); scanf("%I64d",&m); cal(m); printf("%I64d\n",ans); return 0; }
[Codeforces 258B & 259 D]Little Elephant and Elections 数位dp+dfs,布布扣,bubuko.com
[Codeforces 258B & 259 D]Little Elephant and Elections 数位dp+dfs
原文:http://blog.csdn.net/ahm001/article/details/37591519