The 2024 CCPC National Invitational Contest (Changchun),第17届吉林省赛 C

题解是什么意思呢，首先我们需要知道的是，斐波那契数列可以用矩阵快速幂和矩阵乘法求解 $(F (n + 1) F (n)) = (1110) (F (n) F (n - 1)) = M (F (n) F (n - 1))$ $(F (n + 1) F (n)) = M^{n} (10)$ 题解横着放也是一样的，根绝题解给出的例子，手模一下发现是对的，如何去理解? $T 0$ 是一个单位阵 $E$ ， $T 1$ 和我上面写的矩阵相似, $E$ 和任何矩阵 $A$ 相乘结果都是A，所以可以理解为 $0$ 的贡献是 $E$ ,也就是没有，二进制 $1$ 的贡献则是 $T 1 (M)$ 让斐波那契数列往下递推一次然后题解那个从0 到 $2^{m} - 1$ 的求和答案怎么算出来的呢? 我们需要注意到， $0—— 2^{m} - 1$ 中, 二进制数 $1$ 的个数为 $0$ 的数有 $C_{n}^{0}$ 个二进制数 $1$ 的个数为 $1$ 的数有 $C_{n}^{1}$ 个二进制数 $1$ 的个数为 $2$ 的数有 $C_{n}^{2}$ 个 ...

补题链接

我们通过打表可以验证其正确性，我们把那个题解的式子展开一下 $\sum_{i = 0}^{2^{m} - 1} f (g (i)) = F_{0} \cdot (T_{0} + T_{1})^{m} = F_{0} \cdot (C_{m}^{0} \cdot T_{0}^{0} \cdot T_{1}^{m} + C_{m}^{1} \cdot T_{0}^{1} \cdot T_{1}^{m - 1} + C_{m}^{2} \cdot T_{0}^{2} \cdot T_{1}^{m - 2} + ......)$ 由于 $T_{0}$ 是一个单位阵，所以可以直接拿掉，那么刚好和注意到的和前面的计算贡献的方法对应起来，那么按照题解说的固定前缀即可算出最终答案先贴一份题解代码

#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using i128 = __int128;

constexpr int mod = 1e9+7,maxn = 1e7+2;
string s;
array<int,2> F0={{0,1}};
array<array<int,2>,2> E ={{{1,0},{0,1}}};
array<array<int,2>,2> T1={{{0,1},{1,1}}};
array<array<int,2>,2> T ={{{1,1},{1,2}}};
array<array<int,2>,2> t[maxn];
array<array<int,2>,2> pre[maxn];

array<array<int,2>,2> mul(array<array<int,2>,2> a,array<array<int,2>,2> b) {
    array<array<int,2>,2> res;
    res[0][0]=(1LL*a[0][0]*b[0][0]+1LL*a[0][1]*b[1][0])%mod;
    res[0][1]=(1LL*a[0][0]*b[0][1]+1LL*a[0][1]*b[1][1])%mod;
    res[1][0]=(1LL*a[1][0]*b[0][0]+1LL*a[1][1]*b[1][0])%mod;
    res[1][1]=(1LL*a[1][0]*b[0][1]+1LL*a[1][1]*b[1][1])%mod;
    return res;
}

array<int,2> Mul(array<int,2> a,array<array<int,2>,2> b){
    array<int,2>res;
    res[0]=(1LL*a[0]*b[0][0]+1LL*a[1]*b[1][0])%mod;
    res[1]=(1LL*a[0]*b[0][1]+1LL*a[1]*b[1][1])%mod;
    return res;
}


signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>s;
    int n = s.size();
    pre[0]=t[0]=E;
    t[1]=T;
    pre[1]=T1;
    for(int i = 2;i<=n+1;++i){
        t[i]=mul(t[i-1],T);
        pre[i]=mul(pre[i-1],T1);
    }
    i64 ans = 0;
    int pre1=0;
    for(int i = 0;i<n;++i){
        if(s[i]=='0'){
             continue;
        }else{
            ans = (ans+Mul(F0,mul(pre[pre1],t[n-i-1]))[0])%mod;
            pre1++;
        }
    }
    if(s.back()=='1') ans = (ans+Mul(F0,pre[pre1])[0])%mod;
    else ans = (ans+Mul(F0,pre[pre1])[0])%mod;
    cout<<ans<<'\n';
    return 0;
}

再贴一份队友的代码，队友太会DP了

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using i128 = __int128;

int fb[10000010], n;
string s;
constexpr int mod = 1e9 + 7;
int dp[10000000 + 10][2][2];

void solve()
{
    cin >> s;
    memset(dp, -1, sizeof dp);
    n = s.size();
    dp[n - 1][0][0] = 1;
    dp[n - 1][0][1] = 0;
    if (s.back() == '1'){
        dp[n - 1][1][0] = 1;
        dp[n - 1][1][1] = 0;
    }
    else{
        dp[n - 1][1][0] = 0;
        dp[n - 1][1][1] = 0;
    }
    for (int pos = n - 2; pos >= 0; --pos){
        for (int limit = 0; limit <= 1; ++limit){
            if (limit){
                if (s[pos] == '0'){
                    dp[pos][limit][0] = dp[pos + 1][limit][0];
                    dp[pos][limit][1] = dp[pos + 1][limit][1];
                }
                else{
                    dp[pos][limit][0] = (1ll * dp[pos + 1][0][0] + 1ll * dp[pos + 1][1][0] + 1ll * dp[pos + 1][1][1] + 1) % mod;//这一位取0+对于这一位来说f(n-1)+对于这一位来说f(n-2)+自己这一位是1的贡献
                    dp[pos][limit][1] = (1ll * dp[pos + 1][1][0] + 1ll * dp[pos + 1][0][1]) % mod;//这一位取1+这一位取0
                }
            }
            else{
                dp[pos][limit][0] = (2LL * dp[pos + 1][0][0] + 1ll * dp[pos + 1][0][1] + 1) % mod;
                dp[pos][limit][1] = (1ll * dp[pos + 1][0][0] + 1ll * dp[pos + 1][0][1]) % mod;
            }
        }
    }
    cout << dp[0][1][0]<< "\n";
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    fb[1] = fb[2] = 1;
    for (int i = 3; i <= 1e7; i++)
        fb[i] = (fb[i - 1] + fb[i - 2]) % mod;
    while (t--)
        solve();
    return 0;
}