1565 : 小白的等比数列Ⅱ

时间限制:1 Sec 内存限制:256 MiB 提交:1 正确:1

提交 状态 论坛

题目描述

    由于《小白的等比数列Ⅰ》是一个构造题，所以小白需要给这道题写一个 Special \ Judge（简称 spj，是当一道题有多组解时，用来判断答案合法性的程序）。但是小白太菜了，所以想请你帮忙来写一下这个 Special \ Judge。

    现在小白有一个长度为 n 的序列，他想知道这个序列中有多少个子序列是公比为整数的等比数列（长度为 1 的也算)，你能帮他解决这个问题吗？由于答案可能很大，请将答案对 998244353 取模。

    子序列定义：某个序列的子序列是从最初序列通过去除某些元素但不破坏余下元素的相对位置而形成的新序列，例如序列 [2,3,5] 就是序列 [1,2,4,3,5] 的一个子序列。

输入描述

第一行输入一个整数 n(1 \leq n \leq 10^5)，表示序列的长度。
接下来一行输入 n 个数 a_1,a_2,a_3...a_n(1 \leq a_i \leq 3 \times 10^3) ，表示这个序列。

输出描述

输出一个整数，表示符合条件的子序列的个数。由于答案可能很大，请将答案对 998244353 取模。

样例输入

5
2 4 8 1 3

样例输出

10

提示

这十个符合条件的子序列分别是 [2],[4],[8],[1],[3],[2,4],[2,8],[4,8],[2,4,8],[1,3]。
注意，[2,1] 不是一个符合条件的子序列，因为它的公比是 \frac{1}{2}，不为整数。

来源

WIT第七届新生赛