摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

作法 : 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;     
}