做了好久。。。。

大致思路：

求出前k大的方格之和即为答案，

先考虑一维的情况，设f[i]为数位上各个数相乘为i的数的总数，也就是对于数i,有f[i]个数它们各个位相乘为i，

再拓展到二维，根据乘法原理（貌似是这个原理吧），方格(i , j)的金块数就是f[i] * f[j],

所以先数位DP求出f数组，然后贪心取前k大.

具体过程：

首先观察这道题的特殊性质，可以发现，由于是各个位上的数相乘得到贡献的目标，而各个位上的数只有:

1 2 3 4 5 6 7 8 9(如果有0的话金块就飞出去了，所以可以不算）

那么这几个数的质因子只有2,3,5,7，也就是说不为0的f[i]的i值只有2,3,5,7这4个质因子。

然后用计算器算一下就可以得知满足f[i]不为0的i不会很多，因为2^40就基本超数据范围了,

但是由于n过大，如果连f[i]为0的i也要参与运算就太浪费了，

所以考虑先预处理出可能符合要求的i.

以下提供两种方法：

1,dfs:

从0位开始搜索，

每次都递增（包括自己）的枚举下一位，

如果当前乘积超过n，return (超过n就出去了)

如果当前位==n的位数，统计答案并return（这样的话3会被003之类的统计到）

2，根据质因子只有2,3,5,7,暴力枚举。

4个for分别枚举每种质因子的指数，

退出条件类似于dfs。

 

然后就是DP了。

虽然说已经找到了所有可能状态，但是状态太大了，放不进数组，

怎么办呢？

离散化，每次查询的时候二分一下就好了（当然map也是可以的，不过我不会用23333333）

f[i][j][k]表示dp到第i位，乘积是第j小的那个状态，k=0表示没有超过边界，1表示超过边界。

注意这里的边界是指前i位对比n的前i位是否超过边界（i越大位数越高）

三层for分别枚举i，j，x（下一位是什么）。

每次用当前状态对下一状态做出贡献。

由于是从低位开始枚举的，因此x占的比重更大，

所以根据x来分情况讨论转移方程.

rank表示加上x这位的乘积是第几大

1,若x > s[i+1]（s[i]表示n的第i位）

则不管之前怎么样，都超出边界了

所以f[i+1][rank][1] += f[i][j][1] + f[i][j][0];

2,若x < s[i+1]

则不管之前怎么样，都不会超

所以f[i+1][rank][0] += f[i][j][1] + f[i][j][0];

3,x = s[i+1]

那么下一状态超不超完全取决于当前状态。

所以

f[i+1][rank][0] += f[i][j][0];

f[i+1][rank][1] += f[i][j][1];

然后我们发现对一个数i产生贡献的数的长度可能有很多种，

所以DP完之后，枚举产生贡献的数的长度统计入size[i]

其中长度为len(n的长度)时，

对i造成贡献的数，必须没有超过边界，因此只能加上f[len][i][0].

而其他长度都可以加上f[j][i][0] + f[j][i][1]

这里的size数组实际上就是前面思路里面的f数组，

现在我们得到了size数组，所以下一步就只需要统计答案了。

假设i表示行，j表示列，

显然对于指定的第i行来说，

要依次获得最大，只需要将j指针从大到小依次指向贡献大的列即可（此处size代表了贡献，因为行的限制已经满足了，所以看一个方格的贡献只需要看列，也就是size[列]就可以了）

那么如果我们先对size数组进行排序，那么最优答案必定由前k大的数互相搭配得到。

因此我们定义k个行指针，分别指向自己那一行，同时与这个行指针绑在一起的是一个列指针，先指向贡献最大的那一列，

然后用优先队列按size[行指针] * size[列指针]为标准维护大根堆。

每次取出最大的那一个，取k次，每次取的时候弹出指针，统计贡献，并将列指针移向下一个列（大小仅次于or等于当前列的列），然后放回优先队列中。

最后即可得到答案。

注意此题需要LL，不开会wa。

1 #include
     
        2 using namespace std;  3 #define R register int  4 #define mod 1000000007  5 #define LL long long  6 //#define int LL  7 #define AC 401000  8 int len;  9 int s[15]; 10 LL n,k,tmp,tot,cnt,ans,t;//error!!!tmp是用来放n的，所以也要LL啊 11 LL f[15][AC][2],num[AC],may[AC],size[AC]; 12 struct node{ 13     LL v; 14     int x,y; 15 }; 16  17 bool operator < (node a,node b) 18 { 19     return a.v < b.v; 20 } 21 //1230784859 39640 22 priority_queue 
      
        q; 23 /*观察到实质上是要找到前k大金块最多的方格， 24 然后利用一点组合的知识可以得到： 25 如果用f[i]表示个位数乘积是i的数的个数， 26 那么块(i,j)的方块数就是f[i] * f[j], 27 于是问题变成了求出所有f[i]，并找到任意不重复f[i] * f[j]的最大值， 28 （格子不够就不取了） 29 然后因为金块移动的方式是向个位数乘积移动，而观察这些可能的因数， 30 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9, 31 由这几个数相乘得到的数，它们的质因子只有2 ， 3 ， 5 ， 7。 32 并且观察到2 ^ 40就已经达到了1e12,所以总的有金块的格子不会太多， 33 所以应该可以利用这个来计算？ 34 每个数都用2 ^ a * 3 ^ b * 5 ^ c * 7 ^ d来表示(这样大概就存的下了？) 35 所以就是要对每个可能的数求凑它有多少种方案 36 f[i][j][k][l]四维DP，分别表示各个质因数的次方 37 实际上f只要开大概f[40][29][20][15]就可以了 38 不过因为总状态不多，所以可以先找到所有状态？ 39 然后就按照数位DP的套路来，一位代表到了哪一位，一位是有没有在边界上， 40 这里还加一位表示是哪个数。 41 f[i][j][k]表示到了第i位，乘积是第j小的那个数（相当于离散化），k表示是否超过了n（也就是边界） 42 */ 43  44 bool cmp(int a,int b) 45 { 46     return a > b; 47 } 48  49 void dfs(int x,int length,LL mul)//当前位，当前长度，当前乘积，因为要保证小于n，error!!!mul要开LL啊 50 {
   //其实也不用在意这里搜到的状态是否严格满足大小关系，如果不满足下面反正统计不到的 51     if(!mul || mul > n) return ;//所以直接从小到大枚举防止重复组合即可,貌似手算可以发现，满足条件的mul一定不会大于n？ 52     if(length == len)//为了防止过多无用搜索，只搜到这一位就行了 53     {
   //事实上就是因为这里搜到的状态并不严格满足大小关系，所以这样搜才不会遗漏，比如03这里直接乘会变成0 54     //然而貌似并不会，这就是从第0位开始的原因了吧 55         num[++cnt]=mul;//所以搜到03的假等价条件为搜到13，虽然实际上n不一定大于这个，但是为了保证正确性 56         return;//多搜一点也没关系 57     } 58     for(R i=x;i<=9;i++) 59         dfs(i,length+1,mul * i); 60 }//其实也可以按照原来的思路，直接枚举每个质因子的指数 61 //其实从低位开始枚举也是有用的，因为这样是为了能搜到个位数 62 void pre() 63 { 64     scanf("%lld%lld",&n,&k); 65     tmp=n; 66     while(tmp) 67     { 68         s[++len]=tmp % 10; 69         tmp /= 10; 70     } 71     dfs(0,0,1); 72     sort(num+1,num+cnt+1);     73     for(R i=1;i<=cnt;i++) 74         if(num[i] != num[i+1]) num[++tot]=num[i];//去重 75 } 76  77 inline int half(LL x)//二分这个数的下标error！！！x也要LL啊 78 { 79     int l=1,r=tot,mid;//是从去重后的开始二分。。。。 80     while(l < r) 81     { 82         mid=(l + r) >> 1; 83         if(x == num[mid]) return mid;//error明明是和num[mid]比较。。。。 84         if(x > num[mid]) l=mid + 1; 85         else r=mid; 86     } 87     return l; 88 } 89      90 void work() 91 { 92     f[0][1][0]=1;//原因类似dfs,1的话就可以任意搭配了 93     for(R i=0;i
       
         s[i+1]) f[i+1][rank][1] += f[i][j][1] + f[i][j][0];//如果是大于的话，由于是在高位，所以不管前面怎么样都是大于了100                 else if(x < s[i+1]) f[i+1][rank][0] += f[i][j][1] + f[i][j][0];//同理，此处不管前面怎么样都是小于101                 else//如果是等于的话大小关系就只受前面影响了102                 {103                     f[i+1][rank][1] += f[i][j][1];104                     f[i+1][rank][0] += f[i][j][0];105                 }106             }107         }108     for(R i=1;i<=tot;i++)//枚举数字109     {110         for(R j=1;j
       
      
     

由于本人有打注释的习惯，所以看上去可能有点乱，以下为无注释版本：

1 #include
      
         2 using namespace std;  3 #define R register int  4 #define mod 1000000007  5 #define LL long long  6 #define AC 401000  7 int len;  8 int s[15];  9 LL n,k,tmp,tot,cnt,ans,t; 10 LL f[15][AC][2],num[AC],may[AC],size[AC]; 11 struct node{ 12     LL v; 13     int x,y; 14 }; 15  16 bool operator < (node a,node b) 17 { 18     return a.v < b.v; 19 } 20  21 priority_queue 
       
         q; 22  23 bool cmp(int a,int b) 24 { 25     return a > b; 26 } 27  28 void dfs(int x,int length,LL mul) 29 { 30     if(!mul || mul > n) return ; 31     if(length == len) 32     { 33         num[++cnt]=mul; 34         return; 35     } 36     for(R i=x;i<=9;i++) 37         dfs(i,length+1,mul * i); 38 } 39  40 void pre() 41 { 42     scanf("%lld%lld",&n,&k); 43     tmp=n; 44     while(tmp) 45     { 46         s[++len]=tmp % 10; 47         tmp /= 10; 48     } 49     dfs(0,0,1); 50     sort(num+1,num+cnt+1);     51     for(R i=1;i<=cnt;i++) 52         if(num[i] != num[i+1]) num[++tot]=num[i]; 53 } 54  55 inline int half(LL x) 56 { 57     int l=1,r=tot,mid; 58     while(l < r) 59     { 60         mid=(l + r) >> 1; 61         if(x == num[mid]) return mid; 62         if(x > num[mid]) l=mid + 1; 63         else r=mid; 64     } 65     return l; 66 } 67      68 void work() 69 { 70     f[0][1][0]=1; 71     for(R i=0;i
        
          s[i+1]) f[i+1][rank][1] += f[i][j][1] + f[i][j][0]; 78                 else if(x < s[i+1]) f[i+1][rank][0] += f[i][j][1] + f[i][j][0]; 79                 else 80                 { 81                     f[i+1][rank][1] += f[i][j][1]; 82                     f[i+1][rank][0] += f[i][j][0]; 83                 } 84             } 85         } 86     for(R i=1;i<=tot;i++) 87     { 88         for(R j=1;j