E - Sum

  1. 云栖社区>
  2. 博客>
  3. 正文

E - Sum

angel_imp 2016-03-22 16:48:00 浏览480 评论0

摘要: 传送门 password: nefu 题目如下: 题目大意: 就是给你一个数 n 让你将它拆分成 i份的方案数,并且将这方案数 记为S(i),让求的就是S(i)的和,注意一下数据范围,非常滴大呀。

传送门

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;
}



【云栖快讯】一站式开发者服务,海量学习资源免费学  详情请点击

网友评论