import java.util.Scanner;

public class D639 {

public static void main(String[] args) {

double a = 1., b = 1., c = 1., sum = 0.;

Scanner input = new Scanner(System.in);

while (input.hasNextInt()) {

int n = input.nextInt();

if (n <= 3) {

System.out.println(1);

} else {

for (int i = 4; i <= n; i++) {

sum = a + b + c;

a = b;

b = c;

c = sum;

sum%=10007;    //本來沒這行，這行是後來才加的，還是過不了

}

System.out.print((int)sum);

}

sum = 0;

a = 1;

b = 1;

c = 1;

}

input.close();

}

}

請問，自己跑沒問題，可是交卷後卻愈時，要怎麼解決?

n的值超過10^9不可能迴圈跑10億次不逾時的

我看過一篇文章求費氏數列第 n 個，也是 n 的值超過10^9的

該文章介紹的解法是

2列1欄的向量<f(n+2),f(n+1)> = 2x2陣列Ａ 乘上  2x1的向量<f(n+1),f(n)> = .... = Aⁿ 乘上  2列1欄的向量<f(2),f(1)>即< 1 , 1 >

其中 A 陣列為 1 1

                    1 0

所以重點是求 A陣列的 n 次方，當然是不跑 n 次迴圈，而是用二進位的方式

我又看過一篇介紹求數字 Xⁿ 的二進位法，好像類似以下方式，

假設 n = 11 轉成二進位1 0 1 1 則 x¹¹可以改為 ( ( (1*x)² )² *x )² *x  註： 由左至右遇1時*x

若數字太大會取模，例如 mod = 10..07

以下是以二進位法求Xⁿ取mod後的示意程式碼，例如求 12345的2345678次方後被100007除後的餘數？

int binpow(int x , int n , int mod)

{

假設已將 n 轉為 b[0]~b[k-1]的二進位

  p=1;

  for(i=0; i<k; ++k)
  {
      p = p*p%mod;
      if(b[i]) p*x%mod;
  }

  return p;

}

以上只是憑印象給的意見，還沒確認，若有錯誤請見諒！

剛貼上才發現有一篇 Big Mod 的解題心得可以參考

http://zerojudge.tw/ShowThread?postid=10758&reply=0