ACdream 1007 a + b (数学+快速幂)

左手的ㄟ右手 2022-06-13 01:18 200阅读 0赞

题目链接：  
[ACdream 1007 ][ACdream 1007]

题目：  
![这里写图片描述][SouthEast]  
![这里写图片描述][SouthEast 1]

题解：这个快速幂的相乘会爆long long，用快速乘就可以了。  
不说了….看代码吧…

AC代码：

/*
    * this code is made by LzyRapx
    * Problem: 1007
    * Verdict: Accepted
    * Submission Date: 2017-06-22 17:43:18
    * Time: 176MS
    * Memory: 1664KB
    */
    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const ll mod = 10000000007LL;
    
    ll Multi(ll a, ll b)//a*b
    {
        ll ans = 0;
        while(b)
        {
            if(b&1){
                ans = (ans + a) % mod ;
            }
            a = (a<<1) % mod;
            b>>=1;    
        }
        return ans%mod ;
    }
    
    ll BigMulti(ll ans , ll K)
    {
        if(ans == 0 && K ==0)return 1;
        if(ans == 0)return 0;
    
        ll res = 1;
        while(K)
        {
            if(K&1){
                res = Multi(ans,res);
            }
            ans = Multi(ans , ans);
            K >>= 1; 
        }
        return res%mod ;
    }
    ll N,K;
    int main()
    {
        int t ;
        scanf("%d",&t);
        while(t--)
        {
            scanf("%lld%lld",&N,&K);
            ll res = 0, ans;
            for(int i=1;i<=N;i++)
            {
                scanf("%lld",&ans);
                ans %= mod;
                ans = (ans + mod ) % mod;
                res = (res + BigMulti(ans,K)%mod + mod) % mod; 
            }
            printf("%lld\n",res); 
        }
        return 0;
     }

[ACdream 1007]: http://acdream.info/problem?pid=1007
[SouthEast]: /images/20220613/1b8548a16ee64bc59e050d3dc487b896.png
[SouthEast 1]: /images/20220613/e2ff32ec2f904aed86d5ab77f06b26d3.png