作法 : D&C 與 數學

當我們要放入1~N 的數字時,又要做 “∧”形排列

我們逐步放入1~N 這些數字 每個數字都有2種選擇 放左或放右

但是N最後沒得選 所以只有1種

因此答案就是(2^N) % 1234567

但是2^N方必須用D&C跑 不然會跑很久

所以將N轉成二進位作次方相乘! (在此就不多說了)

/***********************************************************/

#include<stdio.h>  
#include<stdlib.h>  
long long int f(int m,int n, int mod)  
{      
  long long int mul=m;      
  long long int r=1;      
  while(n)  
   {      
      if(n&1)  r*=mul,r%=mod;  
      mul*=mul,mul%=mod,n/=2;      
   }      
  return r;      
}  
main()  
{  
  int N;
  while(scanf("%d",&N)==1)
     if(N!=0)
     printf("%d\n",f(2,N-1,1234567));
     else puts("0");
 return 0;     
}