本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-09 15:21:54

• 题目大意：从1号格子开始，每次可以跳跃到$i+a_i \times x$且$ \leq N$的位置。
• 题目分析

根据题意可以得出一个dp的方程 $dp[j]+=dp[i+a_i \times x]$ 时间复杂度$O(N^2)$

考虑优化：

$j=i+a_i \times x (x>=1)$

这里面$a_i$有可能相同，可能重合的线，这些线可以合并处理。 如果$a_i$互不相同，可以用类似埃筛的方法完成。 $a_i$大的时候直接处理。 $a_i$小的时候可以合并，通过前缀或后缀完成。$a_i$选多大呢，一般选$\sqrt n$。

• 如果 $a_k > \sqrt n$,直接枚举，时间复杂度为$ o(\sqrt n)$
• 如果$a_k \leq \sqrt n$ 时间复杂度$ o(\sqrt n)$预处理前缀和。

计算 $i=ak \times x+k$
$dp[i]=\sum(dp[k]) $ 如何找符号要求的k呢？
枚举已知$i，ak$，找到符合要求的$k $ ?

$k=i-ak \times x=i\%a_k $的数;令$j=a_k$，那么 $sum[j][i\%j]$存储了这样能到达$i$的$a_k$和$k$的对应情况

例如：i=11的时候，可以由哪些点转移而来呢？

        sum[1][0] 1+x;2+x,..,10+x
	sum[2][1] 1+2x,3+2x,..
	sum[3][2] 2+3x,5+3x..
	sum[4][3] 3+4x,7+4x..
	sum[5][1] 1+5x，6+5x..
	....
	sum[10][1] 1+10x... 

通过前缀和转移。
4+3x  sum[3][1]
5+3x  sum[3][2]
7+3x  这就可以与前面的4+3x合并处理sum[3][1] 

参考代码

#include<bits\/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int N=200005,M=400;
int n,a[N];
ll dp[N],sum[M][N],ans=0;\/\/sum[m][n]  kx+b 
int main() {
	scanf("%d",&n);
	for(int i=1; i<=n; i++)
		scanf("%d",&a[i]);
	dp[1]=1;
	for(int i=1; i<=n;i++) {
		for(int j=1;j<M;j++){\/\/枚举前面符合要求的ak的前缀和 sum[ak][i] 
            dp[i]+=sum[j][i%j],dp[i]%=mod; 
        }
        ans=(ans+dp[i])%mod;
        \/\/维护前缀和 
		if(a[i]<M){
			sum[a[i]][i%a[i]]+=dp[i],sum[a[i]][i%a[i]]%=mod;
		}		 
		else{
			for(int j=i+a[i]; j<=n; j+=a[i])
				dp[j]+=dp[i],dp[j]%=mod;
		} 
	}
	printf("%lld\n",ans);
	return 0;
}