欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2019牛客暑期多校训练营(第一场) B Integration (公式推导)

程序员文章站 2022-06-16 17:30:13
...

2019牛客暑期多校训练营(第一场) B Integration (公式推导)

2019牛客暑期多校训练营(第一场) B Integration (公式推导)

 

高中都学过等差数列的裂项吧,这里就是用裂项来化简式子,把相乘的式子化为相减的式子,问题就得到简化。假设n=3,数值分别为a,b,c。推导过程请看下图:

 

2019牛客暑期多校训练营(第一场) B Integration (公式推导)

2019牛客暑期多校训练营(第一场) B Integration (公式推导)

注意有些相乘的地方会溢出,时刻取模。

(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
*/

 

相关标签: 数学 公式推导