LightOJ 1213 - Fantasy of a Summation（排列组合+ 快速幂函+快速乘）

爱被打了一巴掌 2024-04-17 05:51 25阅读 0赞

有n个数，  
选k个，可以重复选取，  
所有可能的结果和是多少。

普通想法就是， 找到所有选取的方法， 然后求总和。

对于选k位，每一位有n中选法，所以一共有nk中结果。

每一位是 a\[i\]的结果有nk-1种， 一共有n个数。  
所以这个一位的总和 是 sum1 = ∑(1~n)   nk-1\*a\[i\]  
一共有k位， 所以答案 ans = sum1 \* k;

#include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    ll qmul(ll a, ll n, ll mod)
    { 
        ll ans = 0;
    
        while(n)
        { 
            if(n%2)
            { 
                ans=(ans+a)%mod;
            }
            a = (a+a)%mod;
            n/=2;
        }
    
        return ans;
    }
    
    ll qpow(ll a, ll n, ll mod)
    { 
        ll ans = 1;
    
        while(n)
        { 
            if(n&1)ans= a*ans%mod;
    
            a = a*a%mod;
            n>>=1;
        }
    
        return ans;
    }
    ll a[35555];
    int main()
    { 
        ios_base::sync_with_stdio(false);
    
        int T, cnt = 0;
        cin>>T;
    
        while(T--)
        { 
            ll n, k, Mod, ans(0);
    
            cin>>n>>k>>Mod;
    
            for(ll i = 0 ;i < n;i++)cin>>a[i];
    
            ll tim = qpow(n, k-1, Mod);
    
    
            for(ll i = 0;i < n;i++)
            { 
                ans = (ans+qmul(a[i], tim, Mod))%Mod;
            }
    
            ans = qmul(ans, k, Mod);
    
            cout<<"Case "<<++cnt<<": "<<ans<<endl;
    
        }
    
        return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 LightOJ 1213 - Fantasy of a Summation（排列组合+ 快速幂函+快速乘）

n个数，选k个，可以重复选取，所有可能的结果和是多少。普通想法就是，找到所有选取的方法，然后求总和。对于选k位，每一位有n中选法，所以一共有nk中...

爱被打了一巴掌/ 2024年04月17日 05:51/ 0 赞/ 26 阅读

相关数论-快速幂、矩阵快速幂、慢速乘

文章目录快速幂矩阵快速幂慢速乘例题 HDU-2817 HDU-3117 XUJC-1395 快

朱雀/ 2023年03月05日 09:41/ 0 赞/ 16 阅读

相关快速组合排列算法

\--- 如何从一个整数数列中，快速的查找出一个子集合，使得这个子集的整数和等于一个给定的目标数值？解决这个问题的算法核心是：快速遍历整数集合的子集合。考虑

古城微笑少年丶/ 2022年08月09日 13:56/ 0 赞/ 14 阅读

相关 lightoj 1006 矩阵快速幂

1006 - Hex-a-bonacci <table> <tbody> <tr> <td title="normal judge"><a href="ht

素颜马尾好姑娘i/ 2022年07月28日 01:09/ 0 赞/ 98 阅读

相关【板子】gcd、exgcd、乘法逆元、快速幂、快速乘、筛素数、快速求逆元、组合数

转载至：[http][][://www.cnblogs.com/flipped/p/5716603.html][http] 1.gcd in

清疚/ 2022年06月16日 08:28/ 0 赞/ 227 阅读

相关快速幂，矩阵快速幂（模板）

1，整数快速幂： C++ Code <table style="width:100%;font-family:Consolas, 'Courier New';font-

左手的ㄟ右手/ 2022年06月11日 03:57/ 0 赞/ 312 阅读

相关 lightOJ 1052 String Growth(矩阵快速幂，找规律)

String Growth Zibon just started his courses in Computer science. After having some l

超、凢脫俗/ 2022年06月09日 08:49/ 0 赞/ 210 阅读

相关快速乘 + 快速幂 + 取模

& 与运算 9&5可写算式如下： 00001001 (9的二进制补码)&00000101 (5的二进制补码) 00000001 (1的二进制补码) 9&5=1

忘是亡心i/ 2022年06月08日 09:38/ 0 赞/ 176 阅读

相关组合数学 (一): 快速幂运算

快速幂快速幂运算 C语言实现应用快速幂运算普通幂运算复杂度为 O(N) 快速幂运算复杂度为 O(lgN) 举个例子: 如

谁践踏了优雅/ 2022年03月21日 08:58/ 0 赞/ 289 阅读

相关矩阵/整数快速幂/乘

参考来源： [整数快速乘法，整数快速幂，矩阵快速幂【参考博客】][Link 1] [参考题目 poj 3070][poj 3070] 先说明一下基本的数学常识： >

朱雀/ 2022年03月10日 03:44/ 0 赞/ 284 阅读