ABC 335 F Hop Sugoroku

题意
https://atcoder.jp/contests/abc335/tasks/abc335_f

题解
显然想到dp，我们首先会产生一个最为朴实的想法，我们设dp[i]为以第i格作为结尾的方案数。那么考虑状态转移，有:dp[i]=∑dp[j](1≤j<i,i≡j(mod a[j]))。这样的做法显然是N方的，不能通过。考虑优化，我们已知a[i]≤2e5的，那么我们考虑一点:i≡j(mod a[j])的另一种表示方法是i=j+k*aj那么这个枚举时间复杂度是O(N/a[i])的，当a[j]很大时，枚举的次数其实是很少的。而考虑dp的另外一种转移:我们现在令b[i][j]表示在模i余j时这个位置的方案数，这或许很绕，我们形式化解释一下:现在有所有的位置x，且x满足x%i==j，那么b[i][j]=∑dp[x]。注意这里的x不是指某一个位置，而是一群满足性质的位置集合这个要在过程中进行，不可预处理。
现在考虑其时间复杂度，对于现在某个要转移的dp[i]，其余数个数是O（a[i]）级别的，那么这个转移是O（a[i]）的。所以如果我们穿插两种方法进行所有位置的状态转移，总的时间复杂度为:O(N(N/V+V))，求导可以得到最优时间复杂度：当我们设置阈值为V=sqrt(N),那么总的时间复杂度为O(Nsqrt(N))，可以通过，这也是所说的根号分治。具体实现的话对于当前要转移的dp[i]，如果当前位置的a[i]大于等于V，那么我们采取第一种转移方法(可用刷表法实现);对于小于V的情况，我们采取第二种转移方法。
在转移之前，先把dp[i]用第二种方法给算出来。剩下的细节就看代码吧

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
const int maxn=1e6+10;
const int mmm=1e3+10;
int n;
int a[maxn],dp[maxn],b[mmm][mmm];

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin>>n;
	int ans=0;
	int s=sqrt(n);
	dp[1]=1;
	for(int i=1;i<=n;i++)
	{
		int a;
		cin>>a;
		for(int j=1;j<=s;j++)
		   dp[i]=(dp[i]+b[j][i%j])%mod;
		if(a<=s)  b[a][i%a]=(b[a][i%a]+dp[i])%mod;
		else 
		{
			int p=i;
			while(p+a<=n)
			{
				p+=a;
				dp[p]=(dp[p]+dp[i])%mod;
			}
		}
		ans=(ans+dp[i])%mod;
	}
	
	cout<<ans;
	
	
	return 0;
 }