AT_abc335_f [ABC335F] Hop Sugoroku-动态规划-前缀优化
wflengxuenong
·
·
个人记录
- 题目大意：从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$选多大呢，一般选$\sqrt n$。
- 如果 $a_k > \sqrt n$,直接枚举，时间复杂度为$ o(\sqrt n)
- 如果a_k \leq \sqrt n 时间复杂度 o(\sqrt n)预处理前缀和。
计算 i=ak \times x+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]
```
参考代码
```cpp
#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;
}
```