Sum HDU - 4704题解

goodmarket · 2018-12-03 17:02:42 · 个人记录

链接:[https://cn.vjudge.net/problem/HDU-4704#author=0]()

题意:S(k)为使得(x1+x2+....+xk)=N有不同解的数量,其中对于固定的N,所以对于(S1+S2+S3+...+Sk)=2^n-1,所以题目求2^(n-1)mod(10^9+7)。

思路:由于N<=10^100000,数据量很大，所以先用费马小定理化简由于m=10^9+7为素数所以可得2^(m-1)mod(m)=1,由此可得2^(n-1)mod(m)=2^(n-m)2^(m-1)mod(m)=2^(n-m)=2^(n-m-(m-1))2^(m-1)mod(m)=...=2(n-m-k(m-1))mod(m)。当n-m-k(m-1)<(10^9+7)时用快速幂求解,而剩余数就是n-1/m时的余数。

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int mod=1e9+7;
char n[100001];
int len;
long long int sum;
long long int ksm()
{
    long long int temp=sum,result=1,x=2;
    while(temp)
    {
        if(temp&1)
        result=result*x%mod;
        x=x*x%mod;
        temp>>=1;
    }
    return result;
}
int main()
{
    int i=0;
    char ch;
    while(scanf("%s",n)!=EOF)
    {
        len=strlen(n);
        for(i=0;i<len;i++)
        {
            sum=(10*sum+n[i]-'0')%(mod-1);
        }
        sum--;
        cout<<ksm()<<endl;
        sum=0;
    }
    return 0;
}