Codeforces Round #157 (Div. 2) D. Little Elephant and Elections(数位DP+枚举)

数位DP部分，不是很难。DP[i][j]前i位j个幸运数的个数。枚举写的有点搓。。。
  1 #include <cstdio>
  2 #include <cstring>
  3 using namespace std;
  4 #define LL __int64
  5 #define MOD 1000000007
  6 int dp[21][21];
  7 int p[21],num;
  8 int o[21];
  9 int dfs(int pos,int pre,int bound)
 10 {
 11     int ans,i,end;
 12     ans = 0;
 13     if(pos == -1)
 14     return pre == 0;
 15     if(!bound&&dp[pos][pre] != -1)
 16     return dp[pos][pre];
 17     end = bound ? p[pos]:9;
 18     for(i = 0;i <= end;i ++)
 19     {
 20         if(i == 4||i == 7)
 21         ans += dfs(pos-1,pre-1,bound&&i == end);
 22         else
 23         ans += dfs(pos-1,pre,bound&&i == end);
 24     }
 25     if(!bound)
 26     dp[pos][pre] = ans;
 27     return ans;
 28 }
 29 void CL(int m)
 30 {
 31     num = 0;
 32     while(m)
 33     {
 34         p[num++] = m%10;
 35         m /= 10;
 36     }
 37 }
 38 int main()
 39 {
 40     int i,m;
 41     int a1,a2,a3,a4,a5,a6,sum;
 42     LL ta1,ta2,ta3,ta4,ta5,ta6;
 43     LL ans,t1,t2;
 44     memset(dp,-1,sizeof(dp));
 45     scanf("%d",&m);
 46     CL(m);
 47     for(i = 0;i <= 9;i ++)
 48     {
 49         o[i] = dfs(num-1,i,1);
 50     }
 51     o[0] --;
 52     ans = 0;
 53     for(a1 = 0;a1 <= 9;a1 ++)
 54     {
 55         ta1 = o[a1];
 56         o[a1] -- ;
 57         for(a2 = 0;a2 <= 9&&o[a1] >= 0;a2 ++)
 58         {
 59             ta2 = o[a2];
 60             o[a2] -- ;
 61             for(a3 = 0;a3 <= 9&&o[a2] >= 0;a3 ++)
 62             {
 63                 ta3 = o[a3];
 64                 o[a3] -- ;
 65                 for(a4 = 0;a4 <= 9&&o[a3] >= 0;a4 ++)
 66                 {
 67                     ta4 = o[a4];
 68                     o[a4] -- ;
 69                     for(a5 = 0;a5 <= 9&&o[a4] >= 0;a5 ++)
 70                     {
 71                         ta5 = o[a5];
 72                         o[a5] -- ;
 73                         for(a6 = 0;a6 <= 9&&o[a5] >= 0;a6 ++)
 74                         {
 75                             ta6 = o[a6];
 76                             o[a6] -- ;
 77                             sum = a1 + a2 + a3 + a4 + a5 + a6;
 78                             if(sum <= 9&&o[a6] >= 0)
 79                             {
 80                                 t1 = ta1;
 81                                 t1 = t1*ta2%MOD;
 82                                 t1 = t1*ta3%MOD;
 83                                 t1 = t1*ta4%MOD;
 84                                 t1 = t1*ta5%MOD;
 85                                 t1 = t1*ta6%MOD;
 86                                 t2 = 0;
 87                                 for(i = sum+1;i <= 9;i ++)
 88                                 t2 += o[i];
 89                                 ans = (ans + t1*t2)%MOD;
 90                             }
 91                             o[a6] ++ ;
 92                         }
 93                         o[a5] ++ ;
 94                     }
 95                     o[a4] ++ ;
 96                 }
 97                 o[a3] ++ ;
 98             }
 99             o[a2] ++;
100         }
101         o[a1] ++ ;
102     }
103     printf("%I64d
",ans);
104     return 0;
105 }