题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5086
题目大意：给出长度为n的数组，然后要求累计里面的每个子串的和。
解题思路：这道题直接枚举肯定不行，所以要找递推关系。
假设：{1,2,3,4}为某一个序列，假设我们已经找到了{1,2,3}，接下来把{4}加入进去；
由于{1,2,3}已经有{1},{2},{3},{1,2},{2,3},{1,2,3},那么我们需要观察，把{4}放进去会有哪些影响，
首先会多出{3,4},{2,3,4},{1,2,3,4},{4}，这是突破口，我们只要找到[k,3]的所有和，再把{4}给补上即可。
这样我们就有递推式：dp[i] = dp[i-1] + tmp[i-1] + i * a[i]，其中dp[i]表示前i个序列的子串和，tmp[i]表示sum{[k,i]}，k-i的总和。
由于要取模，所以必须把所有的数都要变成__int64，这里WA若干次。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 447005;
const int mod = 1e9+7;
int n;
__int64 a[maxn],dp[maxn],tmp[maxn];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i = 1; i <= n; i++)
scanf("%I64d",&a[i]);
dp[1] = tmp[1] = a[1];
for(int i = 2; i <= n; i++)
tmp[i] = (tmp[i-1] + i * a[i] % mod) % mod;
for(int i = 2; i <= n; i++)
dp[i] = (dp[i-1] + tmp[i-1] + i * a[i] % mod) % mod;
printf("%I64d\n",dp[n]);
}
return 0;
}