Nemlit 的博客

Nemlit 的博客

By a konjac

题解 CF468C 【Hack it!】

posted on 2019-10-15 17:07:30 | under 题解 |

构造题果然都非常神仙啊

~~首先翻译有点问题, $L, R$ 的范围应该为 $[1, 10^{200}]$ ~~

由于模数a达到了 $10^{18}$ ,所以我们可以发现,当 $i<10^{18}$ 时, $f()$ 有一个性质:

$$ f(i+10^{18}) = f(i)+1$$

我们令 $g=\sum_{i=1}^{10^{18}}f(i)\ (mod\ a)$

于是我们有: $g+1=\sum_{i=2}^{10^{18}+1}f(i)\ (mod\ a)$

$g+a-g=\sum_{i=a-g+1}^{10^{18}+a-g}f(i)\ (mod\ a)=0\ (mod\ a)$

所以我们可以构造出一组解为 $[a-g, 10^{18}+a-g+1]$

于是我们现在问题就变成了求出 $g$

$g=\sum_{i=1}^{10^{18}-1}f(i)+1$

对于 $10^{18}-1$ 的所有数位出现次数都是一样长的

所以答案应该为 $45*$ 每一个数位出现多少次

这个东西就可以用数位DP组合数来求了:我们把原问题想象成:有18个空位,你可以放 $[0, 9]$ 中的所有数,问 $i$ 放了多少次

$$ans=\sum_{i=1}^{18}C_{18}^i*9^{18-i}$$ 然后用 $__int128$ 跑一下,答案为 $45*18*10^{17}+1=81*10^{18}+1$

$Code:$

#include<bits/stdc++.h>
using namespace std;
long long a, pax = 1e18 + 1;
signed main() {
    cin >> a;
    long long l = a - pax % a * 9 % a * 9 % a, r = pax + l - 1;
    printf("%lld %lld", l, r);
    return 0;
}