2019牛客暑期多校训练营(第一场) B Integration (公式推导)
程序员文章站
2022-06-16 17:30:13
...
高中都学过等差数列的裂项吧,这里就是用裂项来化简式子,把相乘的式子化为相减的式子,问题就得到简化。假设n=3,数值分别为a,b,c。推导过程请看下图:
注意有些相乘的地方会溢出,时刻取模。
(PS:又是自闭的一场。。。。。)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N= 1e3+10;
const ll mod = 1e9+7;
ll a[N],ans,temp;
int n;
ll poww(ll a,ll b)
{
ll res=1;
while(b)
{
if(b&1) res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}
int main(void)
{
while(~scanf("%d",&n))
{
ans=0;
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
for(int i=1;i<=n;i++)
{
temp=1;
for(int j=1;j<=n;j++)
{
if(i==j) continue;
temp=(temp*((a[j]*a[j]-a[i]*a[i])%mod))%mod;
//这里乘之前取模,不然会被样例卡
}
ans=(ans+poww(temp,mod-2)*poww(2*a[i],mod-2)%mod)%mod;
}
printf("%lld\n",(ans%mod+mod)%mod);
}
return 0;
}
/*
1
1
1
2
2
1 2
*/
/*
500000004
250000002
83333334
*/
推荐阅读
-
2020牛客暑期多校训练营(第一场)Easy Integration
-
2020牛客暑期多校训练营(第一场)B Infinite Tree 虚树
-
2019牛客暑期多校训练营(第一场) B Integration (公式推导)
-
2019牛客暑期多校训练营(第一场)Integration
-
2019牛客暑期多校训练营(第二场) - B - Eddy Walker 2 - BM算法
-
2019牛客暑期多校训练营(第二场)F,H,A,D,B
-
2019牛客暑期多校训练营(第一场)A Equivalent Prefixes 单调栈
-
题解 | Crazy Binary String-2019牛客暑期多校训练营第三场B题
-
2020牛客暑期多校训练营(第一场)Easy Integration
-
2020牛客暑期多校训练营(第一场)B Infinite Tree 虚树