题解 | 牛妹的位运算

//归纳法,原理我在学；
//(1) [0,2)=4^0;[2,4)=4^1;[4,8)=4^2;......
//(2) [0,2)=4^0;[0,4)=[0,2)+[2,4);[0,8)=[0,2)+[2,4)+[4,8);......
void solve() {
    vector<ll> vec(100001,1);
    for (int i = 3; i <= 100000; i++) {
        vec[i] = vec[i-1]*4%MOD;//(1)
    }
    for (int i = 2; i <= 100000; i++) {
        vec[i] = (vec[i] + vec[i - 1]) % MOD;//(2)
    }
    ll l; cin >> l;cout << vec[l];
}