[ccAUG14] Mountain Holidays 2

描述 Description

Let’s remember the problem Mountain holidays (MOU1H). The story of Mountain holidays is the following. Some time ago, Chef discovered that more and more people have started climbing mountains every day. So he decided to build a restaurant in the Ukrainian resort Bukovel (Carpathian Mountains). But there are many places to choose, so he wants to choose the best one.

By your great helps, Chef could find to the best place to build a restaurant, now Chef becomes rich. Now he wants to build a restaurant in the next mountain. Similar to previous one, the next mountain is described by a sequence of N points. Here the points are numbered from 1 to N, and the height of point k is denoted by Hk. Every two adjacent points of the mountain are connected by a segment.

For example, the mountain described by N = 9, H = [0, 2, 1, 2, 1, 3, 0, 1, 0] is like a following:

`        /
 /        /

In the mountain, all of the tourists will go from the point 1 to point N.

For comfort of the tourists, Chef has bought teleports too. Using a teleport, a tourist can be transferred from point i to point j, for all i < j. Of course, tourists can also walk from point i to point i+1 on foot.

Now Chef wants to calculate the attractiveness of the mountain, as the number of the different climbs.

A climb is defined by the nonempty sequence (p1, p1+1), (p2, p2+1), …, (ps, ps+1) of the moves on foot , where pk+1 ≤ pk+1 for k = 1, 2, …, s − 1.

Two climbs, say (p1, p1+1), (p2, p2+1), …, (ps, ps+1) and (q1, q1+1), (q2, q2+1), …, (qt, qt+1) are different if and only if

s ≠ t or

There exists at least one k such that 1 ≤ k < min(s, t) and Hpk+1 – Hpk ≠ Hqk+1 – Hqk.

You are given the array H, find the number of the different climbs that exist on the mountain. Since the answer can be very large, output it modulo 109+9 = 1000000009.

输入格式 InputFormat

The first line of input contains T, denoting the number of test cases. Then T test cases follow.

The first line of each test case contains an integer N, denoting the number of points on the mountain.

On second line of each test case, there are N space-separated integers H1, H2, …, HN, denoting the height of each point.

输出格式 OutputFormat

For each test case, output an integer denoting the number of the different climbs modulo 109+9 = 1000000009.

样例输入 SampleInput

1 2 3 4 5 6
0 2 1 2 1 3 0 1 0
0 5 -5 5 -5 4 -4

样例输出 SampleOutput


CodeChef MOU2H



#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define ll long long
const ll mod=1000000009;
ll i,j,t,n,m,r,k,z,y,x;
ll T,ans;
ll a[1100005],f[1100005],last_o[9000005];
ll *last=last_o+4100005;
int main()
    while (T--)
        for (i=1;i<=n;i++) scanf("%lld",&a[i]);
        if (n==1)
        for (i=1;i<=n;i++) a[i]=a[i+1]-a[i],last[a[i]]=0;
        for (i=1;i<=n;i++)
            if (last[a[i]]) f[i]=(f[i]-f[last[a[i]]-1])%mod;
            else f[i]++;
    return 0;