[蓝桥杯 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;
  }