打表不难发现，序列的长度以及序列中1的个数都是斐波那契数列。因为第 i 秒1的个数由 i - 1的1和 i - 2的0变换而来，那么f[i] = f[i - 1] + f[i - 2]。序列的长度同理，第 i 秒的序列长度由 i - 1秒的长度加上 i - 1 秒的1变换而来，而i - 1秒的1的个数就是 i - 2 秒的序列长度。
至此这道题已经做完了，但题解中有一个大佬还详细的证明，具体看这里。
然后这题读了前面的字母会迷之GG，后面全RE，不读就AC.
1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #include<algorithm> 5 #include<cstring> 6 #include<cstdlib> 7 #include<cctype> 8 #include<vector> 9 #include<stack> 10 #include<queue> 11 using namespace std; 12 #define enter puts("") 13 #define space putchar(' ') 14 #define Mem(a, x) memset(a, x, sizeof(a)) 15 #define rg register 16 typedef long long ll; 17 typedef double db; 18 const int INF = 0x3f3f3f3f; 19 const db eps = 1e-8; 20 const int maxn = 93; 21 inline ll read() 22 { 23 ll ans = 0; 24 char ch = getchar(), last = ' '; 25 while(!isdigit(ch)) last = ch, ch = getchar(); 26 while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar(); 27 if(last == '-') ans = -ans; 28 return ans; 29 } 30 inline void write(ll x) 31 { 32 if(x < 0) x = -x, putchar('-'); 33 if(x >= 10) write(x / 10); 34 putchar(x % 10 + '0'); 35 } 36 37 ll f[maxn]; 38 //char c[10]; 39 40 int main() 41 { 42 f[1] = f[2] = 1; 43 for(int i = 3; i < maxn; ++i) f[i] = f[i - 1] + f[i - 2]; 44 //scanf("%s", c); //?????????????????? 45 ll q = read(); 46 while(q--) 47 { 48 ll a = read(), b = read(); a--; 49 ll ans = 0; 50 for(int i = 91; i >= 0; --i) 51 { 52 if(a >= f[i] && b >= f[i]) a -= f[i], b -= f[i]; 53 else if(a >= f[i]) a -= f[i], ans -= f[i - 1]; 54 else if(b >= f[i]) b -= f[i], ans += f[i - 1]; 55 } 56 write(ans), enter; 57 } 58 return 0; 59 }