黒く塗られたマスの集合と駒の進め方とは対応するので、ありうる駒の進め方を数え上げれば良いです。

このもとで、今回の問題を計算量を気にせずに解くことを考えましょう。以下のような擬似コードの DP を書くことになると思います。

dp={1,0,...,0};
for(i=1;i<=N;i++)
  for(j=i+A[i];j<=N;j+=A[i])
    dp[j]+=dp[i];
print(sum(dp));

\(A_i\) が大きいケースでは \(j\) ループが回る回数は少なく済むのでこの方針がそのまま使えそうですが、例えば \(A_i=(1,1,\dots,1)\) のようなケースでは \(O(N^2)\) の時間計算量を要するので、このままではこの問題に正解することは難しいです。

では、 \(A_i\) が小さいケースについて \(dp\) 配列を高速に更新する方法を考えましょう。

\(i<j\) について、 \(dp[i]\) から \(dp[j]\) に遷移させる条件は、 \((j-i)\) が \(A_i\) の倍数であること ( すなわち、 \(i\) を \(A_i\) で割ったあまりと \(j\) を \(A_i\) で割ったあまりとが一致すること ) です。

このことから、 \(dp2[d][r] = \) { \(d\) で割った余りが \(r\) である場合 } のような配列を作ればこの問題を解くことができそうです。( 実際に、この方針から正解することができます。 )

では、 \(A_i\) が小さい、大きいとはどのようなことでしょうか?
仮に、 \(A_i \le b\) が \(A_i\) が小さいか大きいかの境界であったとしましょう。

• \(A_i\) が小さい場合の処理をかけるとその部分の時間計算量は全体で \(O(Nb)\)
• \(A_i\) が大きい場合の処理をかけるとその部分の時間計算量は全体で \(O(N \times \frac{N}{b})\)

となります。 \(O(Nb + N \times \frac{N}{b})\) の評価をなるだけ良くするには、 \(b=\sqrt{N}\) とすればよいです ( 略証: 相加相乗平均の関係 ) 。
実装上では、 \(b\) を \(\sqrt{\max N}\) 付近の適当な定数にしてしまっても構いません。また、各部分の定数倍によっては、最適な \(b\) が \(\sqrt{N}\) から少し遠い値になることもあるので、局面によっては色々試すのも良いでしょう。

ここから正しい実装に辿り着くのは読者への課題とします。解説の最後に実装例を示します。

このように、問題を \(\sqrt{N}\) を境に区切ったり、 \(\sqrt{N}\) 個に問題を分割して部分問題を高速に解いたりするテクニックを 平方分割 と呼ぶことがあります。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

#define mod 998244353
#define BD 500

int dp[200005]={0};
int dp2[505][505]={0};

int main(){
  int n;
  cin >> n;
  dp[0]=1;
  for(int i=0;i<n;i++){
    int a;
    cin >> a;
    for(int d=1;d<=BD;d++){
      dp[i]+=dp2[d][i%d];
      if(dp[i]>=mod){dp[i]-=mod;}
    }

    if(a<=BD){
      dp2[a][i%a]+=dp[i];
      if(dp2[a][i%a]>=mod){dp2[a][i%a]-=mod;}
    }
    else{
      for(int j=i+a;j<n;j+=a){
        dp[j]+=dp[i];
        if(dp[j]>=mod){dp[j]-=mod;}
      }
    }
  }

  int res=0;
  for(int i=0;i<n;i++){
    res+=dp[i];
    if(res>=mod){res-=mod;}
  }
  cout << res << "\n";
  return 0;
}

注: \(998244353\) での除算を条件分岐を利用して回避しています。