hdu 4704 Sum【组合数学/费马小定理/大数取模】By cellur925
发布时间:2020-12-14 04:20:58 所属栏目:大数据 来源:网络整理
导读:首先,我们珂以抽象出S函数的模型:把n拆成k个正整数,有多少种方案? 答案是C(n-1,k-1)。 然后发现我们要求的是一段连续的函数值,仔细思考,并根据组合数的性质,我们珂以发现实际上答案就是在让求2^(n-1)。 然鹅我们并不能高兴地过早。因为n的数量级竟然
首先,我们珂以抽象出S函数的模型:把n拆成k个正整数,有多少种方案? 答案是C(n-1,k-1)。 然后发现我们要求的是一段连续的函数值,仔细思考,并根据组合数的性质,我们珂以发现实际上答案就是在让求2^(n-1)。 然鹅我们并不能高兴地过早。因为n的数量级竟然到了丧心病狂的1e100000.连高精度都救不了它。
?* Update:其实这是扩展欧拉定理。思考了一上午后来被大佬告知这是一个定理... 定理可戳这位大佬的文章。 那么对于本题。我们就求$2^{{n-1}%{p-1}}%p$就行了...还要大数取膜...恶心。 $Code$ 1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 5 using namespace std; 6 typedef long long ll; 7 const ll moder=1e9+7; 8 9 char seq[200000]; 10 11 ll ksm(ll a,ll b) 12 { 13 ll ans=1; 14 while(b) 15 { 16 if(b&1) ans=ans*a%moder; 17 b>>=1; 18 a=a*a%moder; 19 } 20 return ans; 21 } 22 23 int main() 24 { 25 while(scanf("%s",seq+1)!=EOF) 26 { 27 ll m=moder-1; 28 ll tmp=0; 29 int len=strlen(seq+1); 30 for(int i=1;i<=len;i++) 31 { 32 tmp=tmp*10+seq[i]-‘0‘; 33 if(tmp>=m) tmp=tmp%m; 34 } 35 tmp=(tmp-1+m)%m; 36 printf("%lldn",ksm(2,tmp)); 37 } 38 return 0; 39 } ? (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |