[蓝桥杯 2025 国 B] 斐波那契字符串一一题解

[P12833 蓝桥杯 2025 国 B] 斐波那契字符串 - 洛谷 (luogu.com.cn)
本题为2025.6.15号蓝桥国CB真题，笔者在此做一个记录。比赛中笔者想出来了，但是晚上复盘时发现在计算代码中：int c=(x%M+y%M)%M，在比赛中忘记对这里的加法取模了，导致加法这里到后续会爆，悲…，一失足成千古恨，希望大家引以为戒TT

• (S_{n-2}) 内部的逆序对：数量为 fib[n-2]。

• (S_{n-1}) 内部的逆序对：数量为 fib[n-1]。

• 跨部分逆序对：(S_{n-2}) 中的每个 ‘1’ 与 (S_{n-1}) 中的每个 ‘0’ 配对。

• ones_{n-2} 为 (S_{n-2}) 中 ‘1’ 的数量，等于斐波那契数 (F_{n-3})。

• zeros_{n-1} 为 (S_{n-1}) 中 ‘0’ 的数量，等于斐波那契数 (F_{n-3})。

• 因此跨部分数量为 ((F_{n-3})^2)，即代码中的 c * c（其中 c = F_{n-3}）。

//ACcode
#include <iostream>
#define int long long
using namespace std;
const int N=1e5+10;
const int M=1e9+7;
int fib[N];
void fibc(){fib[1]=0,fib[2]=0,fib[3]=0,fib[4]=1;int x=0;int y=1;for(int i=5;i<=100000;i++){int c=(x%M+y%M)%M;fib[i]=((c%M*c%M)%M+(fib[i-2]%M+fib[i-1]%M)%M)%M;x=y;y=c;}
}
signed main()
{fibc();int t;int n;cin>>t;while(t--){cin>>n;cout<<fib[n]<<endl;}return 0;
}