【Tyvj1091】等差数列

2014-05-25
竞赛题解 / 动态规划
TYVJ

描述 Description

等差数列的定义是一个数列 S，它满足了 (S[i]-S[i-1]) = d (i>1)。显然的一个单独的数字或者两个数字也可以形成一个等差数列。

经过一定的学习小 C 发现这个问题太简单了，等差数列的和不就是 (Sn+S1)*n/2？因为这个问题实在是太简单了，小 C 不屑于去解决它。这让小 C 的老师愤怒了，他就找了另外一个问题来问他。

小 C 的老师给了他一个长度为 N 的数字序列，每个位置有一个整数，他需要小 C 帮他找到这个数字序列里面有多少个等差数列。

这个问题似乎太难了，小 C 需要你的程序帮他来解决这个问题。

输入格式 InputFormat

第一行一个整数 N，表示老师给出的数字序列的长度。
第二行有 N 个整数 A[i]，表示数字序列每个数字的大小。

输出格式 OutputFormat

输出只有一行一个整数，表示这个序列中的等差数列的个数（mod 9901）。

样例输入 SampleInput

10
221 177 171 -377 182 -61 178 -150 12 -491

样例输出 SampleOutput

55

数据范围和注释 Hint

对于 30% 的数据，N <= 100.
对于 70% 的数据，N <= 500.
对于 100% 的数据，N <= 1000；-500 <= A[i] <= 500

Tyvj 1091

代码 Code

水。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define mod 9901
#define inf 0x7fffffff/27.11
int a[1001];
int f[1001][3001];
int i,j,t,n,m,l,r,k,z,y,x,xmax,xmin,ans;
int main()
{
    scanf("%d",&n);
    xmin=inf;xmax=-inf;
    for (i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        xmax=max(x,xmax);
        xmin=max(x,xmin);
    }
    for (i=1;i<=n;i++) for (j=i+1;j<=n;j++) 
    {
        t=a[j]-a[i]+1000;
        f[j][t]+=f[i][t]+1;
        f[j][t]%=mod;
    }
    ans=n;
    for (i=1;i<=n;i++) for (j=0;j<=3000;j++) ans=(ans+f[i][j])%mod;
    printf("%d\n",ans);
    return 0;
}