现在的位置: 首页 > 综合 > 正文

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.

题目大意:

给一个长度为n的数列,求有多少个子序列不是等差数列。此题将空序列和只有一个元素的序列看做等差数列。

Output

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

Constraints

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

Example

Input:

2
1
1
3
1 2 1

Output:

0
1

题解

有点奇怪的dp,求“不是”可以化为“全部”-“是”。全部可用快速幂求,然后因为a[i]很小,所以可以用f[i][j]表示以i结尾,公差为j的(长度大于等于2)的等差数列个数。

#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;
}

抱歉!评论已关闭.