CF468C 【Hack it!】

构造题果然都非常神仙啊

首先翻译有点问题，\(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;

}

巴特西

CF468C 【Hack it!】

\(Code:\)

最新文章

热门文章