Sum （HDU - 4704）隔板定理 组合数求和 费马小定理（2^(N-1)%(1e9+7) N巨大）

                                                               Sum

                         Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
                                          Total Submission(s): 4338    Accepted Submission(s): 1765

 

Problem Description

 

Sample Input

2

 

Sample Output

2

 

Hint

1. For N = 2, S(1) = S(2) = 1. 2. The input file consists of multiple test cases.

 

Source

2013 Multi-University Training Contest 10

题解

此题的大意是：给出一个N，得出N被分成1、2、3 . . . N个数的情况之和，然后对1e9+7取余

以4为例：S(1) = 1（4）、S(2) = 3 （1+3，3+1，2+2）、S(3) = 3（1+1+2， 1+2+1，2+1+1）、

S(4) = 1（1+1+1+1）。所以N=4时求的是 （1+3+3+1）%（1e9+7）

那么问题来了，这个S(1)+S(2)+. . . +S(N)怎么求呢？

这里就联系到高中（还是初中来着。。忘了）数学知识——隔板定理，如下图所示

N=4可以看成4个小球，S(1)就是将这4个小球分成一组，也就是在4个小球中间的三个空隙中不插板子，组合数为C(3,0)；S(2)就是将这4个小球分成两组，也就是插一个板子，组合数为C(3,1)。同理S(N)就是插N-1个板子（分成N组），组合数为C(N-1,N-1)。

下面的问题就是怎么求他们的和了，数学符号有点难打。。就手写了，字丑凑乎看吧。。。

简化了很多有木有，那么新的问题来了，题上可知N最大为10的1000000次，而longlong最多也就10的18次（大概。。记不清了），那怎么求这超级无敌雷霆霹雳大的次幂呢？

费马小定理登场！

定理内容：假如p是质数，且gcd(a,p)=1（也就是a不为p的倍数），那么 a^(p-1)≡1（mod p）

由题可知，1e9+7是个质数，2是整数，a与p互质显而易见，所以现在我们的目的就是想办法把2^(N-1)%(1e9+7)降幂为2^k%(1e9+7)

已知a^(p-1) = 1，且n可能很大很大，就看N-1里包括多少个p-1，把这些都丢掉求剩下的就好。假设有x个p-1（p=1e9+7）则：2^(N-1) = 2^(x*(p-1)) * 2^k = 1^x * 2^k = 2^k，所以直接求2^k就好，k = (N-1)%(p-1)

由于N过于长，就用字符串存储，之后边转化为数边取余，最后减1即可。

还有就是处理过后的N也不小，求次幂时用快速幂会减很多不必要的重复时间

# include <cstdio>
# include <cstring>
# include <algorithm>
# define mod 1000000007

using namespace std;

typedef long long ll;
const int maxn = 1000000;
char n[maxn];
 
ll quick_pow(ll a, ll k) 
{
    ll ans=1;
    while(k)
    {
        if(k&1)
        {
            ans=(ans*a)%mod;
            k--;
        }
        k/=2;
        a=a*a%mod;
    }
    return ans;
}

int main()
{
	while(~scanf("%s",n))
	{
		ll len = strlen(n);
		ll mod1 = mod-1;
		ll k = n[0]-'0';
		for(ll i=1;i<len;i++) k = (k*10 +(n[i]-'0')) % mod1;
		
		k -= 1;
		printf("%lld\n",quick_pow(2,k));
	}
	return 0;
}