题意：对于一个数列A，substring是一个连续子串，subsequence是其非连续子序列。对于一个数字序列，记它的diversity是它的最大元素减去最小元素的差。给出一个数字序列，求与它diversity相同的substring和subsequence各有多少个。比如若A为1，4，3，4，则答案为3和6。
解法：组合数学问题。首先，记A中最大元素为ma，最小元素为mi，且最大元素有s1个，最小元素有s2个，数列A长度为n。
则A的所有subsequence共有2^n个，不含ma的subsequence有2^(n-s1)个，不含mi的subsequence有2^(n-s2)个，mi和ma都不含的有2^(n-s1-s2)个，由容斥原理，所求为2^n - 2^(n-s1) - 2^(n-s2) + 2^(n-s1-s2)个。
对于substring的个数，选取的的substring为A[begin] 到 A[end]，枚举end从0到n-1，并且用t1记录目前位置最后出现的mi的位置，t2记录目前最后出现的ma的位置，则对于每个枚举的end，ans += min(t1, t2)。详见代码。
比赛的时候没有想清楚，substring个数的求法写得好复杂。。。后来看了男神代码自己默默模仿了一份。。。。
tag:组合数学，counting
/*
* Author: Plumrain
* Created Time: 2013-12-03 19:43
* File Name: math-LA-5990.cpp
*/
#include <iostream>
#include <cstdio>
#include <algorithm> using namespace std; typedef long long int64;
const int64 mod = ;
const int N = ; int64 g[N], a[N];
int64 min(int64 a, int64 b) {return a > b ? b : a;}
int64 max(int64 a, int64 b) {return a > b ? a : b;} int main()
{
g[] = ;
for (int i = ; i < N; ++ i)
g[i] = g[i-] * % mod; int T, n;
scanf ("%d", &T);
while (T--){
int64 mi = mod, ma = ;
scanf ("%d", &n);
for (int i = ; i < n; ++ i){
scanf ("%lld", &a[i]);
mi = min(mi, a[i]);
ma = max(ma, a[i]);
} int64 ans1 = , ans2 = ; if (mi == ma){
ans1 = ((int64)(n + ) * n / ) % mod;
ans2 = g[n] - ;
printf ("%lld %lld\n", ans1, ans2);
continue;
} int t1 = -, t2 = -, s1 = , s2 = ;
for (int i = ; i < n; ++ i){
if (a[i] == mi){
++ s1; t1 = i;
}
if (a[i] == ma){
++ s2; t2 = i;
} ans1 = (ans1 + min(t1+, t2+)) % mod;
} ans2 = (g[n] - g[n-s1] - g[n-s2] + g[n-s1-s2]) % mod;
if (ans2 < ) ans2 += mod;
printf ("%lld %lld\n", ans1, ans2);
}
return ;
}