阿祁的部落格

ZeroJudge b525- 先別管這個了，你聽過turtlebee嗎？解題心得( 題目 )

解題概念:費氏數列、建表

注意:這個不是最好的方法，只是相對快速冪比較容易理解。

解題方法:如果我們先把題目改為初始沒有男裝，我們可以發現最後的總數跟費氏數列有關連(倍數)，而男裝其實就是女裝但是少了一天(需要一天變成女裝型態)，所以我們其實可以分開算，但是數字很大，所以我們一開始直接建個大小為2*10^5的陣列，才不會TLE(根據題目要求，若從頭1000次絕對會超時)，結果發現這樣MLE(大概70MB，題目要求64MB)，但是我們可以再把空間除以二，作法是只儲存數列的偶數位(例如:1 1 2 3 5 8 13，則存1_ 2 _ 5 _ 13)，其中奇數位可以透過球後的兩個偶數位相減求得，並不會增加程式運行的時間，也省了一半的記憶體。

註:儲存費氏數列用int，但計算時最好轉成long，不然可能溢位，另外我EOF的方式其實寫得不太妥當(只是判斷如果輸入都是0(null)就break)，應該要修正

參考程式碼( 如果有更好意見可在下方留言，以做為本文章之補充，感謝! )

import java.io.*;
import java.util.*;
public class zjb525 {
	public static int ret,r;
	public static long retl;
	public static int[] f=new int[10000005];
	public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	public static void main(String[] args) throws Exception {
		BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
		f[0]=1;
		int temp=1;
		for(int i=1;i<10000005;i++) {
			f[i]=(temp+f[i-1])%100000007;//建表
			temp=(temp+f[i])%100000007;
		}
		long m,fm;
		int k;
		while(true) {
			m=readnum();
			fm=readnum();
			k=(int)readnum();
			if(m+fm+k==0)break;//EOF
			bw.write((m*query(k)+fm*query(k+1))%100000007+"\n");
		}
		bw.flush();
	}
	
	public static long readnum() throws Exception {//輸入
		ret=0;
		r=br.read();
		while(r>47&&r<58) {
			ret*=10;
			ret+=(r&15);
			r=br.read();
		}
		return ret;
	}
	
	public static long query(int x) {//查詢費氏數列
		if(x%2==0) {
			return (long)f[x/2]; 
		}
		retl=(long)f[(x+1)/2]-(long)f[x/2];
		if(retl<0)retl+=100000007L;
		return retl;
	}

}