题目描述
Given an array A with length n a[1],a[2],...,a[n] where a[i] (1<=i<=n) is positive integer.
Count the number of pair (l,r) such that a[l],a[l+1],...,a[r] can be rearranged to form a geometric sequence.
Geometric sequence is an array where each term after the first is found by multiplying the previous one by a fixed, non-zero number called the common ratio. i.e. A = [1,2,4,8,16] is a geometric sequence.
输入描述:
The first line is an integer n (1 <= n <= 100000).
The second line consists of n integer a[1],a[2],...,a[n] where a[i] <= 100000 for 1<=i<=n.
输出描述:
An integer answer for the problem.
示例1
输入
5 1 1 2 4 1
输出
11
说明
The 11 pairs of (l,r) are (1,1),(1,2),(2,2),(2,3),(2,4),(3,3),(3,4),(3,5),(4,4),(4,5),(5,5).
示例2
输入
10 3 1 1 1 5 2 2 5 3 3
输出
20
备注:
The answer can be quite large that you may use long long in C++ or the similar in other languages.
题解
暴力。
先统计公比为$1$的区间有几种，接下来，无论公比为多少，区间长度不会超过$17$，因此只要枚举区间起点，验证$17$个区间即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 100000 + 10;
int n;
long long a[maxn];
long long b[maxn];
int sz;
int check() {
if(b[0] == b[sz - 1]) return 0;
if(sz == 2) return 1;
for(int i = 2; i < sz; i ++) {
if(b[1] * b[i - 1] != b[0] * b[i]) return 0;
}
return 1;
}
int main() {
while(~scanf("%d", &n)) {
for(int i = 1; i <= n; i ++) {
scanf("%lld", &a[i]);
}
long long ans = 1;
long long sum = 1;
for(int i = 2; i <= n; i ++) {
if(a[i] == a[i - 1]) sum ++;
else sum = 1;
ans = ans + sum;
}
for(int i = 1; i <= n; i ++) {
sz = 0;
for(int j = i; j <= min(n, i + 20); j ++) {
b[sz ++] = a[j];
int p = sz - 1;
while(p && b[p] < b[p - 1]) {
swap(b[p], b[p - 1]);
p --;
}
ans = ans + check();
}
}
printf("%lld\n", ans);
}
return 0;
}