2019牛客暑期多校训练营（第一场）-B.Integration()

旧城等待， 2021-10-01 06:28 357阅读 0赞

链接：https://ac.nowcoder.com/acm/contest/881/B

题意:给出n，和数组a\[n\]，求特定表达式取模后的值。

思路：用到列项相消：![Image 1][]

那么，![Image 1][]，然后就变成了求和问题，利用费马小定理求逆元可计算得到结果。

AC代码：

#include<cstdio>
    using namespace std;
    
    const int MOD=1e9+7;
    typedef long long LL;
    
    int n;
    LL a[1005],c[1005];
    LL ans;
    
    LL qpow(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(){
        while(~scanf("%d",&n)){
            for(int i=1;i<=n;++i)
                scanf("%lld",&a[i]),c[i]=1;
            ans=0;
            for(int i=1;i<=n;++i)
                for(int j=1;j<=n;++j)
                    if(j!=i) c[i]=c[i]*((a[j]*a[j]%MOD-a[i]*a[i]%MOD+MOD)%MOD)%MOD;
            for(int i=1;i<=n;++i)
                ans=(ans+qpow(2*a[i]%MOD*c[i]%MOD,MOD-2))%MOD;
            printf("%lld\n",ans);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/FrankChen831X/p/11213135.html

[Image 1]:

发表评论取消回复

表情：

评论列表（有 0 条评论，357人围观）

还没有评论，来说两句吧...

相关阅读

相关 2019牛客暑期多校训练营（第一场） A Equivalent Prefixes

题意：给你两个数组a，b，大小为n，让你寻找一个数p (1<= p <= n) ，使之在 1~p 任意一个区间中a,b数组的最小值下标相同。分析：方法一：单调栈

水深无声/ 2021年12月03日 21:49/ 0 赞/ 327 阅读

相关 2019牛客暑期多校训练营（第一场）

Solutions -------------------- A：Equivalent Prefixes 题意：若$\\text\{RMQ(u,l,r)=RM

约定不等于承诺〃/ 2021年11月27日 04:44/ 0 赞/ 497 阅读

相关 2019牛客暑期多校训练营第一场

牛客多校还是挺难的。三个人各种白给。题目链接：[https://ac.nowcoder.com/acm/contest/881\question][https_ac.now

朱雀/ 2021年11月10日 15:44/ 0 赞/ 380 阅读

相关 2019牛客暑期多校训练营（第一场）

[题目传送门][Link 1] <table> <tbody> <tr> <td>题号</td> <td>A</td> <td>B</td>

淡淡的烟草味﹌/ 2021年11月06日 01:12/ 0 赞/ 366 阅读

相关 2019牛客暑期多校训练营第六场

题目链接：[https://ac.nowcoder.com/acm/contest/886\question][https_ac.nowcoder.com_acm_contes

今天药忘吃喽~/ 2021年11月02日 13:38/ 0 赞/ 394 阅读

相关 2019牛客暑期多校训练营（第五场）

比赛链接：[https://ac.nowcoder.com/acm/contest/885\question][https_ac.nowcoder.com_acm_contes

左手的ㄟ右手/ 2021年10月26日 18:24/ 0 赞/ 401 阅读

相关 2019牛客暑期多校训练营第一场

牛客多校还是挺难的。三个人各种白给。题目链接：[https://ac.nowcoder.com/acm/contest/881\question][https_ac.now

逃离我推掉我的手/ 2021年10月19日 00:56/ 0 赞/ 413 阅读

相关 2019牛客暑期多校训练营（第一场）-B.Integration()

链接：https://ac.nowcoder.com/acm/contest/881/B 题意:给出n，和数组a\[n\]，求特定表达式取模后的值。思路：用到列项相消：!

旧城等待，/ 2021年10月01日 06:28/ 0 赞/ 358 阅读

相关 2019牛客暑期多校训练营（第一场）

<table> <thead> <tr> <th>Sloved</th> <th align="center">A</th> <th alig

绝地灬酷狼/ 2021年09月30日 02:02/ 0 赞/ 378 阅读

相关 2019牛客暑期多校训练营（第一场）E.ABBA

考虑题目的约束条件对于任何合法情况的前缀应满足 A < = n + B A<=n+B A<=n\+B B < = A + m B<=A+m B<=A\+

谁践踏了优雅/ 2021年09月29日 23:48/ 0 赞/ 378 阅读