## codechef Maxim and Progressions(2014.6月赛)

2018年01月13日 ⁄ 综合 ⁄ 共 2090字 ⁄ 字号 评论关闭

## Problem Description

Maxim likes arithmetic progressions and does not like sequences which are not arithmetic progressions.
Now he is interested in the question: how many subsequences of his sequence a, consisting of n elements, are not arithmetic progressions.
Sequence s[1],  s[2],  ...,  s[k] is called a subsequence of sequence a[1],  a[2],  ...,  a[n], if there will be such increasing sequence of indices i[1], i[2], ..., i[k] (1  ≤  i[1]  <  i[2]  < ...   <  i[k]  ≤  n), that a[i[j]]  =  s[j]. In other words, sequence
s can be obtained from the a by deleting some elements.
Sequence s[1],  s[2],  ...,  s[k] is called an arithmetic progression, if it can be represented as :
s[1] = p, where p — some integer;
s[i] = p + (i - 1)·q (i > 1), where q — some integer.
In particular, the empty sequence or a sequence of one element is an arithmetic progression.

## Input

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.

The first line of each test case contains an integer n — the number of elements in the sequence. The next line of the test case contains n integer, a[1], a[2], ..., a[n] — elements of the sequence.

## Output

For each test case print the remainder of the division the answer on 1000000007 (10^9 + 7). All answers print on different lines.

1 ≤ T ≤ 10
1 ≤ n ≤ 200000
1 ≤ a[i] ≤ 100

2
1
1
3
1 2 1

0
1

## 题解

```#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define MAXN 200005
#define ll long long
#define mod 1000000007
using namespace std;
int T,n,a[MAXN],f[105][205],cnt[105];
ll ans;
void init()
{
scanf("%d",&n);
int i;
for(i=1;i<=n;i++) scanf("%d",&a[i]);
}
ll ksm(int k)
{
ll x=2,sum=1;
while(k)
{if(k&1) sum=(sum*x)%mod;
x=(x*x)%mod;
k=k>>1;
}
return sum;
}
void dp()
{
memset(f,0,sizeof(f));
memset(cnt,0,sizeof(cnt));
int i,j;
ll sum=0;
for(i=1;i<=n;i++)
{for(j=1;j<=100;j++)
f[a[i]][a[i]-j+100]=(f[a[i]][a[i]-j+100]+f[j][a[i]-j+100]+cnt[j])%mod;
cnt[a[i]]++;
}
for(i=1;i<=100;i++)
for(j=1;j<200;j++)
sum=(sum+f[i][j])%mod;
sum=(sum+n+1)%mod;
ans=(ans-sum+mod)%mod;
printf("%lld\n",ans);
}
int main()
{
scanf("%d",&T);
while(T--)
{init();
ans=ksm(n);
dp();
}
return 0;
}```