题意:
题目给了你从任意数中选出三个数，然后相乘，并加到总和的公式，现在要你从任意数中选出四个数，相乘，并加到总和，问最后的答案，对1e9+7取模
思路:
这个题真的是我的锅,赛后被队友好一顿刺激,走入一个死胡同里去了当时,因为给了三项公式,就误导我要去推一个四项的公式...结果五个小时,真的五个小时,我就一直在推,然后死活出不来....
其实这个题真的是很操蛋,先说第一种做法就是dp啊,dp[i][j]为前i个数,任意j项的乘积的和为多少,那么可以推出如下方程:
dp[i][j]=dp[i-1][j]+dp[i-1][j-1]*ai, 然后处理一下边界就行了....
因为我们就求四项的 ,所以j最多为4,复杂度就是O（n）的.
#include<stdio.h>
#include<string.h>
#include<string>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int maxn=1e5+10;
int n;
ll a[maxn];
ll dp[maxn][10];
ll ans;
int main(){
while(~scanf("%d",&n))
{
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
dp[1][1]=a[1];
for(int i=2;i<=n;i++)
{
for(int j=1;j<=min(i,4);j++)
{
if(j==1)
{
dp[i][j]=dp[i-1][j]+a[i];
dp[i][j]%=mod;
}
else
{
dp[i][j]=dp[i-1][j]+dp[i-1][j-1]*a[i];
dp[i][j]%=mod;
}
}
}
printf("%lld\n",dp[n][4]);
}
return 0;
}
另外一种思路是,你要求四项的乘积,给了你三项乘积的和,你要利用起来啊!!! 我们对于第i个数,对于它前面i-1个数,任取三个和它乘起来相加,等价于把ai提出来,前面i-1个数任意三项乘积的和,再乘以ai. 那么这个三项乘积和的公式就有用处了.
(至于i后面那些项还含有ai的由后面的来解决,这样就避免重复了)
复杂度也近似于O(n)的.
我们只需要每算完一项把对应的a[i]加到和里面就可以了....省去了枚举的麻烦.
#include<stdio.h>
#include<string.h>
#include<string>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int maxn=1e5+10;
int n;
ll a[maxn];
ll ans;
ll quick(ll x,ll y)
{
ll res=1;
while(y)
{
if(y&1)
res=res*x%mod;
x=x*x%mod;
y>>=1;
}
return res%mod;
}
ll inv6=quick(6,mod-2);
ll solve(ll x,ll y,ll z)
{
ll s=0;
s=quick(x,3);
s=(s-3*x*y%mod+mod)%mod;
s=(s+2*z)%mod;
return s*inv6%mod;
}
int main(){
while(~scanf("%d",&n))
{
ll x=0,y=0,z=0;
ans=0;
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
if(i>3)
{
ans=(ans+solve(x,y,z)*a[i]%mod)%mod;
}
x=(x+a[i])%mod;
y+=quick(a[i],2);
z+=quick(a[i],3);
y%=mod;
z%=mod;
}
printf("%lld\n",ans);
}
return 0;
}