对于本题，由于访问的次数很大，所以当然得先预处理保存在数组中，然后用的时候就不用一次一次的再重复计算了，本题重在预处理。
- #include <stdio.h>
- #include <string.h>
- #define N 10005
- int p;
- int prim[N];
- int pth[N];
- int inv[N][N];
- bool prime[N];
- int fac[N][N];
- int k=0;
- void isprime()
- {
- int i,j;
- memset(prime,true,sizeof(prime));
- memset(pth,0,sizeof(pth));
- for(i=2;i<N;i++)
- {
- if(prime[i])
- {
- prim[++k]=i;
- pth[i]=k;
- for(j=i+i;j<N;j+=i)
- {
- prime[j]=false;
- }
- }
- }
- }
- int quick_mod(int a,int b,int m)
- {
- int ans=1;
- a%=m;
- while(b)
- {
- if(b&1)
- {
- ans=ans*a%m;
- b--;
- }
- b>>=1;
- a=a*a%m;
- }
- return ans;
- }
- void init()
- {
- int i,j;
- for(int i=1;i<=k;i++)
- {
- fac[i][0]=inv[i][0]=1;
- for(j=1;j<prim[i];j++)
- {
- fac[i][j]=(fac[i][j-1]*j)%prim[i];
- inv[i][j]=quick_mod(fac[i][j],prim[i]-2,prim[i]);
- }
- }
- }
- int C(int n,int m)
- {
- if(m>n) return 0;
- if(m==n) return 1;
- int t=pth[p];
- return fac[t][n]*(inv[t][n-m]*inv[t][m]%p)%p;
- }
- int Lucas(int n,int m)
- {
- if(m==0) return 1;
- return C(n%p,m%p)*Lucas(n/p,m/p)%p;
- }
- int main()
- {
- int n,m,k=1;
- isprime();
- init();
- while(~scanf("%d%d%d",&n,&m,&p))
- {
- if(m<=n/2) m=n-m;
- printf("Case #%d: %d\n",k++,(m%p+Lucas(n+1,m+1)%p)%p);
- }
- return 0;
- }