AT_abc335_f [ABC335F] Hop Sugoroku 题解

比 E 简单。

分析

考虑暴力 DP。

定义状态函数 $f_i$ 表示最后一个黑点为 $i$ 时的方案数，有：$f_i =\sum\limits_{j=1}^{i-1}f_j[(i-j)\bmod val_j =0]$。不难发现在使用刷表法的时候，转移代码：

for(re int j=1;i+val[i]*j<=n;++j) f[i+val[i]*j]=(f[i+val[i]*j]+f[i])%p;

这玩意复杂度是 $O(\frac{n}{val_i})$ 的。

又有一种 DP 方式，定义状态函数 $g_{i,j}$ 表示在枚举到下标 $x$ 时，$k \bmod i =j$ 的方案数。因为 $a \bmod b =c \bmod b$ 时，$(a-c) \bmod b =0$，所以有：$f_i =\sum\limits_{j=1}^{V} g_{j,i \bmod j}$。复杂度 $O(V)$。

然后有个很经典的东西，叫根号分治：对于 $val_i \le V$ 的情况，用第二种 DP 方式，否则使用第一种。有复杂度 $O(nV+n\frac{n}{v})$，$V=\sqrt{n}$ 时接近 $O(n\sqrt{n})$。

代码

#include<bits/stdc++.h>
using namespace std;
#define re register
#define il inline
#define PII pair<int,int>
#define x first
#define y second

il int read(){
	int x=0;char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return x;
}

const int N=2e5+10,M=sqrt(N)+10,p=998244353;
int n,val[N],ans;
int f[N],g[M][M],base;

il void solve(){
	n=read(),base=sqrt(n);
	for(re int i=1;i<=n;++i) val[i]=read();
	f[1]=1;
	for(re int i=1;i<=n;++i){
		for(re int j=1;j<=base;++j) f[i]=(f[i]+g[j][i%j])%p;
		if(val[i]<=base) g[val[i]][i%val[i]]=(g[val[i]][i%val[i]]+f[i])%p;
		else for(re int j=1;i+val[i]*j<=n;++j) f[i+val[i]*j]=(f[i+val[i]*j]+f[i])%p;
		ans=(ans+f[i])%p;
	}
	printf("%d\n",ans);
	return ;
}

signed main(){
	solve();
	return 0;
}