無限序列

題目大意：

有這樣一個規則：1.把“1”變成“10” 2.把“0”變成“1”
一個序列的第一位是“1”
然后是：“10”，“101”……
序列無限次操作后會得到“1011010110110101101……”
問某一個區間內有多少個“1”

原題：

題目描述

我們按以下方式產生序列：
1、 開始時序列是： “1” ；
2、 每一次變化把序列中的 “1” 變成 “10” ，“0” 變成 “1”。
經過無限次變化，我們得到序列"1011010110110101101…"。
總共有 Q 個詢問，每次詢問為：在區間A和B之間有多少個1。
任務 寫一個程序回答Q個詢問

輸入

第一行為一個整數Q，后面有Q行，每行兩個數用空格隔開的整數a, b。

輸出

共Q行，每行一個回答

輸入樣例

1 2 8

輸出樣例

4

數據范圍

$1?Q?50001?a?b<2^{63}$

解題思路：

首先暴力是不可能的
我們可以發現這就是一個斐波那契

1 10 101 10110 10110101 1 1+0 10+1 101+10 10110+101

然后寫上1的個數和長度

1 1 1 10 1 2 101 2 3 10110 3 5 10110101 5 8

可以發現他們都是斐波那契數列，而且長度為下一個數的1的個數
我們就可以先預處理前100項（第100項$?2^{63}$）然后可以用其中的一些項拼成1~A-1&B的1的個數，然后用前綴和原理一減就可以了

代碼：

#include<cstdio> #define ull unsigned long long using namespace std; int n; ull x,y,a[105]; ull ask(ull dep) {ull js,ans=0,now=dep;while (now){js=1;while (a[js+2]<=now) js++;//先找最大的可拼的now-=a[js+1];//減去ans+=a[js];//計算結果}return ans; } int main() {a[1]=1;a[2]=1;for(int i=3;i<=100;++i)a[i]=a[i-1]+a[i-2];//預處理scanf("%d",&n);for (int i=1;i<=n;++i){scanf("%llu %llu",&x,&y);printf("%llu\n",ask(y)-ask(x-1));//前綴和} }

總結

以上是生活随笔為你收集整理的【斐波那契】【前缀和】无限序列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。