目录
F - Hop Sugoroku
题目大意:
思路解析:
代码实现:
F - Hop Sugoroku
题目大意:
思路解析:
容易想到这是一个dp题,然后初始转移方程为:
如果当a[i] 较大时,时间复杂度为 O(N*N/a[i]) 接近于N,但是当a[i]为1时,时间复杂度解决O(N^2),这是不能接受的。
观察dp转移方程可以发现 (j*a[i]+i)% a[i] == i % a[i],即只有当 j % a == i % a时才能转移,这衍生出另一个dp方程 dp2[i][j],表示当前格子在t,a[t] == i, t % a[t] == j。
根据上面分析可以发现dp[i] += dp2[j][i%j],如果dp2开很大的话会爆内存空间,所以我们应该想到,当a[i] 较小时( 我取的是500) 采用dp2进行转移,如果a[i]较大则采用第一种方式进行转移。
这样的会时间开销就变为 O(N*N/500) 约等于 O(N*400)
代码实现:
import java.io.*;
import java.math.BigInteger;
import java.util.*;
public class Main {
static int mod1 = (int) 1e9 + 7;
static int mod2 = 998244353;
static int BD = 500;
public static void main(String[] args) throws IOException {
int n = input.nextInt();
int[] dp = new int[n];
dp[0] = 1;
int ans = 0;
int[][] dp2 = new int[505][505];
for (int i = 0; i < n; i++) {
int a = input.nextInt();
for (int j = 1; j <= BD; j++) {
dp[i] = (dp[i] + dp2[j][i % j]) % mod2;
}
if (a <= BD){
dp2[a][i % a] = (dp2[a][i%a] + dp[i]) % mod2;
}else {
for (int j = 1; j * a + i < n; j++) {
dp[j * a + i] = (dp[j * a + i] + dp[i]) % mod2;
}
}
}
for (int i = 0; i < n; i++) {
ans = (ans + dp[i]) % mod2;
}
out.println(ans);
out.flush();
out.close();
br.close();
}
// -------------------------------- 模板 ---------------------------
static boolean nextPermutation(int[] arr) { // 排列数循环模板 记得使用 do while 循环
int len = arr.length;
int left = len - 2;
while (left >= 0 && arr[left] >= arr[left + 1]) left--; // 从升序 一直往降序排列。
if (left < 0) return false;
int right = len - 1;
// 找到第一个升序的位置,将其改为降序。
while (arr[left] >= arr[right]) right--;
{
int t = arr[left];
arr[left] = arr[right];
arr[right] = t;
}
// 修改后它的前面仍然为降序,将前面全部修改为升序,这样能保证不会漏算,也不会算重
left++;
right = len - 1;
while (left < right) {
{
int t = arr[left];
arr[left] = arr[right];
arr[right] = t;
}
left++;
right--;
}
// System.out.println(Arrays.toString(arr));
return true;
}
public static long qkm(long a, long b, long mod) { // 快速幂模板
long res = 1;
while (b > 0) {
if ((b & 1) == 1) res = (res * a) % mod;
a = (a * a) % mod;
b >>= 1;
}
return res;
}
// // 线段树模板
// public static int lowbit(int x){
// return x & (-x);
// }
//
// public static void bulid(int n){
// for (int i = 1; i <= n; i++) {
// t[i] = a[i];
// int j = i + lowbit(i);
// if (j<=n) t[j] += t[i];
// }
// }
//
// public static void updata(int x, int val){
// while (x <= n){
// t[x] += val;
// x += lowbit(x);
// }
// }
//
// public static int query(int l, int r){
// int res = 0;
// while (l <= r){
// res += a[r];
// r--;
// while (r - lowbit(r) >= l){
// res += t[r];
// r -= lowbit(r);
// }
// }
// return res;
// }
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static Input input = new Input(System.in);
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static class Input {
public BufferedReader reader;
public StringTokenizer tokenizer;
public Input(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream), 32768);
tokenizer = null;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public String nextLine() {
String str = null;
try {
str = reader.readLine();
} catch (IOException e) {
// TODO 自动生成的 catch 块
e.printStackTrace();
}
return str;
}
public int nextInt() {
return Integer.parseInt(next());
}
public long nextLong() {
return Long.parseLong(next());
}
public Double nextDouble() {
return Double.parseDouble(next());
}
public BigInteger nextBigInteger() {
return new BigInteger(next());
}
}
}