庆祝一下我第一次赛时 AC 了 F 题（鼓掌）。
这道题第 1 秒就可以看出是道 dp 的题，并且状态肯定是 \(dp[i]\) 表示最后一个黑色块在 \(i\) 的状态的个数。问题无非在于如何转移状态。
很容易想到两种转移方法：
- 暴力转移法：对于每一个 \(i\)，我们直接暴力将每一个 \(i+a_i\times k\) 进行加法。
- 数组记录法：对于每一个 \(i\) 和 \(a_i\)，我们使用一个数组 \(cnt\) 记录，其中 \(cnt[i][j]\) 表示有 \(a_i=i\) 且开始位置为形如 \(j+i\times k\)（\(k\) 为整数）的方案总数。然后对于每个 \(i\) ，我们直接用 \(cnt\) 里的数累加。
可如上两种方法各有一个问题。暴力转移法由于 \(a_i\) 最小为 \(1\)，则一次最多会跳 \(2\times10^5\) 次，外面还有循环，必超时。数组转移法由于 \(a_i\) 最大为 \(2\times10^5\)，可数组根本开不了这么大。
这时候就有一个绝妙的想法：以 \(10^3\) 为分界线！
插句题外话：当时我觉得这一定是个巧妙的玄学解法，并不是正解，觉得我能想到这个方法真是个天才。赛后看到官方解法，居然也差不多是这样，更觉得我是个天才了。
那就总结一下吧：
- 先计算 \(dp_i\)，由于大于等于 \(10^3\) 的部分已计入，则 \(dp_i+=\sum_{j=1}^{10^3}cnt[j][i\%j]\)。
- 对于 \(a_i < 10^3\)，\(dp[i+a_i \times k]+=dp[i]\)。
- 对于 \(a_i\ge 10^3\)，\(cnt[a_i][i\%a[i]]+=dp[i]\)。
代码如下。赛时代码有点丑，将就看吧。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll MOD=998244353;
// head
const int N=2e5+5,M=1e3+5;
int a[N];
int dp[N];
int cnt[M][M];
signed main()
{
cin.tie(nullptr);
ios::sync_with_stdio(false);
int n;cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
dp[1]=1;
if(a[1]>=M-5) {for(int i=1+a[1];i<=n;i+=a[1]) dp[i]=1;}
else cnt[a[1]][1%a[1]]=1;
for(int i=2;i<=n;i++){
for(int j=1;j<=min(n,M-6);j++){
dp[i]=(dp[i]+cnt[j][i%j])%MOD;
}
if(a[i]>=M-5){
for(int j=i+a[i];j<=n;j+=a[i]) dp[j]=(dp[j]+dp[i])%MOD;
}
else cnt[a[i]][i%a[i]]=(cnt[a[i]][i%a[i]]+dp[i])%MOD;
}
int ans=0;
for(int i=1;i<=n;i++){
ans=(ans+dp[i])%MOD;
}
cout<<ans<<endl;
}