题目链接: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;
}