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