CF468C Hack it! 构造 dp

题面链接

题意：

给你一个 a a a，设 f ( i ) f(i) f(i)表示 i i i这个数十进制下各个数位的数字之和。要你求一对 ( l , r ) (l,r) (l,r)，使得 ∑ i = l r f ( i ) = 0 ( m o d   a ) \sum_{i=l}^rf(i)=0(mod\ a) ∑i=lr​f(i)=0(mod a)。如果有多组合法的 ( l , r ) (l,r) (l,r)，输出任意的一组。 a &lt; = 1 e 18 , l , r &lt; = 1 e 200 a&lt;=1e18,l,r&lt;=1e200 a<=1e18,l,r<=1e200。

题解：

这种可能有多组解的题，我们的思路当然是去构造一组解。我们考虑这个 f f f函数有什么性质。

性质1：

f ( i ) + 1 = f ( i + 1 0 x )   ( i &lt; 1 0 x ) f(i)+1=f(i+10^x)\ (i&lt;10^x) f(i)+1=f(i+10x) (i<10x) 很好理解，加上了 1 0 x 10^x 10x之后相当于在原数前面加了一个 1 1 1和若干个 0 0 0，那么各个数位的数字和增加了 1 1 1。

性质2：

∑ i = x + 1 x + 1 0 y f ( i ) = ∑ i = 1 1 0 y f ( i ) + x   ( x &lt; 1 0 y ) \sum_{i=x+1}^{x+10^y}f(i)=\sum_{i=1}^{10^y}f(i)+x\ (x&lt;10^y) i=x+1∑x+10y​f(i)=i=1∑10y​f(i)+x (x<10y) 这个是在第一个性质的基础上的来的，我们可以把两边都有的那些 f ( i ) f(i) f(i)减去，那么我们就可以发现两边剩余的分别是 1 + 1 0 y 1+10^y 1+10y和 1 1 1， 2 + 1 0 y 2+10^y 2+10y和 2... x + 1 0 y 2...x+10^y 2...x+10y和 x x x。根据第一个性质，左边的每一项的函数值都比右边对应项的函数值大 1 1 1，总共加起来就大了 x x x。

有了这两个性质我们考虑怎么去构造答案。

我们先预处理出一个前缀和中 f ( i ) f(i) f(i)之和，当然我们这里只处理 1 1 1到所有 10 10 10的幂的前缀和结果，处理到 1 e 19 1e19 1e19，于是我们就算一下每个数字都出现了多少次，这样最后再乘上这个数值就可以了。我们考虑有了第二个式子能做什么，我们发现只要我们当前的这个 10 10 10的幂次的前缀和的答案加上一个小于当前幂次的数模 a a a能变成 0 0 0，那么我们就可以构造出一个答案。具体地，我们枚举每一个 y y y，若 a − ∑ i = 1 1 0 y m o d   a &lt; 1 0 y a-\sum_{i=1}^{10^y}mod\ a&lt;10^y a−∑i=110y​mod a<10y，那么我们就可以用第二个公式把当前区间左右端点整体加 a − ∑ i = 1 1 0 y m o d   a a-\sum_{i=1}^{10^y}mod\ a a−∑i=110y​mod a就可以构造出来了。

注意算的时候有些地方可能会爆long long，我们发现这个 f f f的前缀和其实是会爆long long的，但是由于最后我们只关心它模 a a a的答案，所以是可以取模的，就不会爆了。

最后吐槽一下，这个题我写完之后一直在炸long long，然后自己还不知道，小一点的数据就没问题，然后就找了个自己之前写过的数位dp当checker，发现自己写的并没有什么问题，就开始怀疑CF的checker写挂了。结果事实是，我的程序和checker都爆long long了。。。QAQ 再就是，我的这个题解可能和网上说的比较多的题解不太一样，写法上可能难写不少吧，好像别的题解都是一两行的样子。

代码：

#include <bits/stdc++.h>
using namespace std;

unsigned long long a,dp[20][20],mi[20],f[20],l,r;
int main()
{
	cin>>a;
	mi[0]=1;
	for(int i=1;i<=19;++i)
	mi[i]=mi[i-1]*10;
	for(int i=1;i<=9;++i)
	dp[0][i]=1;
	for(int i=1;i<=19;++i)
	{
		for(int j=1;j<=9;++j)
		dp[i][j]=dp[i-1][j]+dp[i-1][j]*9+mi[i];
	}
	for(int i=0;i<=18;++i)
	{
		for(int j=1;j<=9;++j)
		{
			f[i+1]=(f[i+1]+dp[i][j]*j%a)%a;
		}	
		f[i]=(f[i]+1)%a;
	}
	for(int i=0;i<=19;++i)
	{
		if(a-f[i]%a<mi[i])
		{
			l=a-f[i]%a+1;
			r=l+mi[i]-1;			
			break;
		}
	}
	cout<<l<<" "<<r<<endl;
	return 0;
}