hdu 4704 Sum(组合，费马小定理，快速幂)

题目链接http://acm.hdu.edu.cn/showproblem.php?pid=4704；

这个题很刁是不是，一点都不6，为什么数据范围要开这么大，把我吓哭了，我kao......说笑的，哈哈。

一开始题意没看清（老毛病了），然后就以为用N对1e+9取模，因为给的数的范围为10¹⁰⁰⁰⁰⁰

所以只能开数组模拟。错了一发。后来再看题，发现错了，S(n)代表的是将N分成n个数的合的不同种类。

那么求S(n)的方法就是高中数学老师教的隔板法，有点忘了。隔板法是这样的，如果N为5，那么将5写成5个1隔开，就像这样

1 1 1 1 1，顾名思义隔板法就是在中间空格出放板子，现在最左和最右边放个板子，不是空格出。如过要求S(3);那么就在4个空格中找2个放格子，那么每两块板子

间的1加起来就是所分的数字，比如放在第格和第二格，分的就为1 1 3，而所C_N³

就是S(3);那么可的通项C_n^k

那么S(1)+S(2)+S(3)+....S(N)=2^N-1

所以就是求2^N-1(mod)(1e+7);

因为N-1很大所以可以用费马小定理；

费马小定理在p为素数的情况下对任意的整数x都有x^p==x(mod p)

;如果x不能被p整除有x^(p-1)=1(mod p);由于a,b<1e9;所以不能被1e9+7整除，求出了k[n],则a^k[n]%p=a^(k[n]%(p-1))%p;

证明如下： k[n]=m*(p-1)+d;那么a^k[n]%p=a^[(m*(p-1))+d]%p=(a^[m*(p-1)]%p*a^(d)%p)%p;

由费马小定理可知a^(m*(p-1))%p=1; 而d=k[n]%(p-1);得证；

然后再快速幂就行了。

 1 #include<stdio.h>

 2 #include<algorithm>

 3 #include<iostream>

 4 #include<stdlib.h>

 5 #include<string.h>

 6 typedef long long ll;

 7 ll fastmi(ll n);

 8 using namespace std;

 9 ll a[100100];

10 char b[100005];

11 ll c[100100];

12 ll k[100100];

13 const int N=1e9+7;

14 const int M=1e9+6;

15 int main(void)

16 {

17     k[0]=5;

18     k[1]=0;

19     k[2]=0;

20     k[3]=0;

21     k[4]=0;

22     k[5]=0;

23     k[6]=0;

24     k[7]=0;

25     k[8]=0;

26     k[9]=1;

27     ll n,i,j,p,q,l;

28     while(scanf("%s",b)!=EOF)

29     {

30         memset(a,0,sizeof(a));

31         l=strlen(b);

32         ll t=1;

33         for(i=0; i<l; i++)

34         {

35             a[i]=b[l-i-1]-'0';

36         }

37

38         int uu=0;

39         for(i=0; i<l+20; i++)

40         {

41

42

43             a[i]=k[i]+a[i]+uu;

44             uu=a[i]/10;

45             a[i]=a[i]%10;

46         }

47

48         ll ww=1;

49         ll pp=0;

50         for(i=0; i<l+20; i++)

51         {

52             pp=(pp%M+(ww%M*a[i]%M)%M)%M;

53             ww=(ww%M*10%M)%M;

54

55         }//(N-1)modM=(N-1+M)modM,为1e+6;M-1为1e+5;k[]数组存的就为1e+5;

56         ll dd=fastmi(pp);

57         printf("%lld\n",dd);

58     }

59

60     return 0;

61

62

63 }

64

65 ll fastmi(ll n)//快速幂

66 {

67     ll x=1;

68     ll y=2;

69     while(n)

70     {

71         if(n&1)

72         {

73             x=(x%N*y%N)%N;

74         }

75         y=(y%N*y%N)%N;

76         n=n/2;

77     }

78     return x;

79 }

巴特西

hdu 4704 Sum(组合，费马小定理，快速幂)

最新文章

热门文章