E - Sum

简介:

传送门

password: nefu

题目如下:



题目大意:

就是给你一个数 n 让你将它拆分成 i份的方案数,并且将这方案数 记为S(i),让求的就是S(i)的和,注意一下数据范围,非常滴大呀。。。


解题思路:

首先我们要将 S(i)求出来,在这里我们就用到可能是高中学的知识吧,应该是 我记得是,用到的是隔板法(也叫插空法),就是现在这里有 n 个1,我们要求的就是拆成i份,这不就是隔板法麻,现在就是有n个1,有n-1个空。讲一下具体的例子:

当 i = 1的时候  C(n-1,0);——S(1)

当 i = 2的时候  C(n-1,1);——S(2)

当 i = 3的时候  C(n-1,2);——S(3)

...

当 i = n的时候  C(n-1,n-1);——S(n)

所以 :

S(1) + S(2) + S(3) + ... + S(n) = C(n-1,0) + C(n-1,1) + C(n-1,2) + .. + C(n-1,n-1) = 2^(n-1)(利用二项式定理

我们将这个问题解决了,所以现在就是2^(n-1) Mod 1000000007,这个我们可以用欧拉定理,因为 2 与 1000000007互素,所以2^phi(1000000007)%1000000007 == 1,所以2^(n-1) Mod 1000000007就可以转化为

2^((n-1)%phi(1000000007)+phi(1000000007)) Mod 1000000007,这里又涉及了一个大数取模问题,这个可以作为模板,

for(int i=0; i<len; i++)
        ret = (ret*10+(st[i]-'0')) % (MOD-1);
每次取模,每次乘以10就好 因为取模运算可以相加的...,写到这里这个题基本上就已经结束了,最后别忘记在快速幂一下,完事儿,下面就是代码:

上代码:

#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 1e5+5;
const int MOD = 1e9+7;
typedef long long LL;
LL quick_mod(LL a, LL b, LL m)
{
    LL ans = 1;
    while(b)
    {
        if(b&1)
            ans = ans*a%m;
        b>>=1;
        a = a*a%m;
    }
    return ans;
}
LL GetMod(char st[])
{
    LL ret = 0;
    int len = strlen(st);
    for(int i=0; i<len; i++)
        ret = (ret*10+(st[i]-'0')) % (MOD-1);
    ret--;
    return ret;
}
char str[MAXN];
int main()
{
    while(cin>>str)
    {
        LL tmp = GetMod(str);
        cout<<quick_mod(2, tmp, MOD)<<endl;
    }
    return 0;
}



目录
相关文章
List strem sum
List strem sum
42 0
|
机器学习/深度学习
计算sum=1+2...+n,要求number和sum的类型都是int,且sum在32位以内~
计算sum=1+2...+n,要求number和sum的类型都是int,且sum在32位以内~
|
SQL
sum函数
sum函数
143 0
|
文件存储
Sum of Round Numbers
Sum of Round Numbers
130 0
Sum of Round Numbers
面试题:sum=1+2-3+4-5...+m 公式:sum=2-m/2
sum=1+2-3+4-5...+m 公式:sum=2-m/2
799 0
|
存储 算法 C#
算法题丨Two Sum
描述 Given an array of integers, return indices of the two numbers such that they add up to a specific target.
1168 0
|
算法 C#
算法题丨3Sum
描述 Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
1234 0
1. Two Sum
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
784 0
|
索引
Two Sum
Given an array of integers, find two numbers such that they add up to a specific target number.
767 0