fib2.pas

program fib2;
var n, i, t, k: longint;
	a, len: array [1..45] of longint;
procedure gen();
	var i: longint;
	begin
		a[1]:=1;
		a[2]:=0;
		len[1]:=1;
		len[2]:=1;
		for i:=3 to 45 do begin
			a[i]:=a[i-1]+a[i-2];
			len[i]:=len[i-1]+len[i-2];
		end;
	end;
function calc(n, k: longint): longint;
	begin
		calc:=0;
		if n=1 then exit(1);
		if n=2 then exit(0);
		if k=len[n] then
			exit(a[n]);
		if k<len[n-2] then
			exit(calc(n-2, k));
		calc:=a[n-2];
		if k>len[n-2] then
			calc:=calc+calc(n-1, k-len[n-2])
	end;
begin
	gen();
	readln(t);
	for i:=1 to t do begin
		readln(n, k);
		writeln(calc(n+1, k));
	end;
end.

what_the_hell_is_this.md

Giả sử ta muốn thực hiện truy vấn n=5, k=7

Tập F gồm các xâu sẽ gồm:

0: a
1: b
2: ab
3: bab
4: abbab
5: bababbab

Đoạn ta muốn tìm số chữ a là ‘’'bababba‘’'

• Ta có thể thấy bababba được cấu tạo từ phần bab của F[3] và abba của F[4]
• abba của F[4] lại được tạo thành từ ab của f[2] và ba của f[3]
• ba của f[3] lại được tạo thành từ b của F[1] và ab của F[2]
• ab của F[2] được tạo thành từ a của F[1] và b của F[0]

Ta hoàn toàn có thể tính được số chữ a có trong từng xâu F[i] và sau đó dùng hàm đệ quy để tính tổng.