题解 P6400

· · 题解

题目传送门

本题巨大的数据范围仿佛在告诉我们这是一道数位 DP，但是在阅读完题面后却发现自己束手无措。

于是开始写无脑暴力，枚举每个数，然后求位数积，判断。这显然是一种偏离正解的方法，无法进一步进行优化。

换一种想法，如果枚举数不可行，就枚举位数积。记 S 为 x 的位数积，显然对于相同的 S 会对应多个 x。如果通过枚举每一位上的数来确定 S，无异于暴力。因此考虑两种枚举 S 方法：

  1. 枚举 S 中每个数字出现的个数。

    如果直接枚举出现次数，相当于把 18 个位置放进 10 个框，总情况数为 \mathrm{C_{27}^{9}=4686825}，无法再继续进行统计对应 x 的个数，必然超时。

    考虑优化。一个较为显然的结论就是 S\le x。又 1\le A\le B\le 10^{18}，所以 S\times x\le 10^{18}，从而推出 S\le 10^9。

    还有一个结论就是，如果 x 中某一数位上的数为 0，那么 S\times x=0<A\le B，一定不存在于 [A,B] 内。

    因此我们只需考虑把 9 个位置放进 9 个框，总情况数就减为 \mathrm{C_{17}^8=24310}，使得后续的统计成为可能。

  2. 枚举 S 中 2,3,5,7 四个质数出现的个数。

    由于 S 必然是由 0-9 这些数的幂相乘而得的，在第 1 种方法中我们已经得出 0 毫无作用。因此剩下的数除 1 以外在分解质因数后一定是由上述四个质数组成，从而可以推出 S 可以表示成 2^a\times 3^b\times 5^c\times 7^d 的形式的。（\mathrm{a,b,c,d\in N}）

    又因为 S\le 10^9，因此 a\le 29，b\le 18，c\le 12，d\le 10。

    通过相应枚举代码可以得出满足 S\le 10^9 的四元组 (a,b,c,d) 的个数为 5194 种，为后续统计留了较多的时空。

这里着重讲解第 2 种枚举方法后的统计。

首先通过 S,A,B 我们可以得知 x 的范围 L 和 R。

void count(ll mul,int fac)
{
    if(mul>B/mul)return;
    if(fac==4)
    {
        ll L=(A-1ll)/mul+1ll;
        ll R=B/mul;
        ans+=solve(R)-solve(L-1);
        return;
    }
    count(mul,fac+1);
    cnt[fac]++;
    count(mul*c[fac],fac);
    cnt[fac]--;
}

然后考虑通过数位 DP 来求得在 [L,R] 中满足条件的 x 的个数。

设计状态 \mathrm{dp[pos][cnt[0]][cnt[1]][cnt[2]][cnt[3]]}，其中 \mathrm{pos} 表示当前数位，\mathrm{cnt[0-3]} 分别表示还需填入的 2,3,5,7 的数量。

注意 0 对答案的干扰。除了作为前导零以外，为了与上面枚举过程相契合，我们不能在数位上填 0。

ll ans=0;
if(lead)ans+=dfs(pos-1,limit&&a[pos]==0,true);
int up=limit?a[pos]:9;
for(int i=1;i<=up;i++)
{
    if(!enough(i))continue;
    work(i,-1);
    ans+=dfs(pos-1,limit&&i==up,false);
    work(i,1);
}
if(!limit&&!lead)DP=ans;
return ans;

注意 1-9 每个数的组成，如 6=2\times 3，那么填入 6 就会对应地消耗 1 个 2 和 1 个 3。对应关系如下：

const int dig[10][4]={{0,0,0,0},//0位置无实际意义，无需理会
{0,0,0,0},{1,0,0,0},{0,1,0,0},//1 2 3
{2,0,0,0},{0,0,1,0},{1,1,0,0},//4 5 6
{0,0,0,1},{3,0,0,0},{0,2,0,0}};//7 8 9

统计部分要求无最高位限制和前导零。如果所有数位填完后，还要检查是否 4 个质数都已填完。相应部分如下：

if(pos==0)return (!lead)&&check();
ll &DP=dp[pos][cnt[0]][cnt[1]][cnt[2]][cnt[3]];
if(!limit&&!lead&&DP!=-1)return DP;

本题讲解至此就告一段落了，上述代码块中个别函数请读者自行完成，如有疑问请评论提出，欢迎指正。