题解：qoj 9479

Danslapiscine · 2025-11-17 14:40:50 · 题解

因为限制长成了环形的鬼样子，导致一个一个数地填维护限制非常困难，必须将填的过程对每个数同时进行。但是注意到 a_i + (a_{i-1} \& a_{i+1}) 的样子很二进制，可以发现该式上 a 最低位只有限地影响得数最低几位。因此有逐位确定的想法，可以在当前最低位上，对每个数的该位进行填，以凑出 M 的这一位。那么就得到了分讨 M 最低位 + 递归的做法。其中每三位凑出 1 的情况，相当于填 0/1 环列，不能有连续的三个 1 和连续的两个 0。可以递推，矩阵乘法加速。

#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
struct Matrix {
    int a[3][3];
}I, ori, trans;
Matrix operator *(const Matrix &a,const Matrix &b){
    Matrix ret;
    for(int i=0;i<=2;i++) for(int j=0;j<=2;j++){
        ret.a[i][j] = 0;
        for(int k=0;k<=2;k++) ret.a[i][j] = (ret.a[i][j] + 1ll * a.a[i][k] * b.a[k][j] % mod) % mod;
    }
    return ret;
}
Matrix ksm(Matrix s,int cnt){
    Matrix ret = I;
    while(cnt){
        if(cnt & 1) ret = ret * s;
        s = s * s;
        cnt >>= 1;
    }
    return ret;
}

int N, M, S;

map<int,int> f;
int dfs(int M){
    if(f.find(M) != f.end()) return f[M];
    if(M == 0) return 1;
    if(M == 1) return S;
    int s;
    if(M & 1) s = 1ll * dfs((M-1)/2) * S % mod;
    else s = (1ll * dfs(M/2) + dfs(M/2-1)) % mod;
    f[M] = s;
    return s;
}

int main(){
    I.a[0][0] = 1, I.a[1][1] = 1, I.a[2][2] = 1;
    trans.a[1][0] = 1, trans.a[2][1] = 1, trans.a[0][2] = 1, trans.a[1][2] = 1;
    ori.a[0][2] = 1;

    scanf("%d%d",&N,&M);
    ori = ori * ksm(trans, N-3);
    S = ori.a[0][2];
    ori = ori * trans;
    S = (1ll * S + ori.a[0][2] + ori.a[0][1]) % mod;
    ori = ori * trans;
    S = (1ll * S + ori.a[0][1] + ori.a[0][0]) % mod;

    printf("%d\n",dfs(M));

    return 0;
}