まず、以下の問題を考えましょう。本問題を完全に解くことに比べると易しい問題です。

操作 \(2\) を全体で \(K\) 回まで行えるとき、 \(M\) はいくらか？

どのように解けばよいでしょうか？

---

実は、最後 \(K\) 回の操作を操作 \(2\) とするのが最適です。
なぜなら、 \((a\ {\rm AND}\ b)\ {\rm OR}\ c\) は常に \(c\) 以上、 \((a\ {\rm OR}\ b)\ {\rm AND}\ c\) は常に \(c\) 以下 であることより、 \({\rm OR}\) の直後に \({\rm AND}\) が来る操作列についてそれらを入れ替えて最終的な \(x\) が減少しないからです。

以降、 \(M\) は既知であるとします。
操作を後ろから、以下の情報を保持して遡ることを考えます。

• 確定フラグ \(f\)
  • \(f\) の \(k\) bit 目が \(1\) 、またその時に限り、最終的な \(x\) の \(k\) bit 目が \(M\) の \(k\) bit 目と一致することが確定している。

確定フラグが立っていない桁について、以下のように 後ろから操作の種類を決めていく ことができます。

• \(M\) にて \(0\) である桁について
  • 今着目している \(A_i\) にてその桁が \(0\) であるとき … (a)
    • \({\rm AND}\) を取ると確定フラグが立ち、 \({\rm OR}\) を取ると確定フラグは立たないままです。
  • 今着目している \(A_i\) にてその桁が \(1\) であるとき … (b)
    • \({\rm AND}\) を取ると確定フラグが立たないままで、 \({\rm OR}\) を取ることは許されません。
• \(M\) にて \(1\) である桁について
  • 今着目している \(A_i\) にてその桁が \(0\) であるとき … (c)
    • \({\rm AND}\) を取ることは許されず、 \({\rm OR}\) を取ると確定フラグは立たないままです。
  • 今着目している \(A_i\) にてその桁が \(1\) であるとき … (d)
    • \({\rm AND}\) を取ると確定フラグが立たないままで、 \({\rm OR}\) を取ると確定フラグが立ちます。

この確定フラグを key とした DP のような方針を考えましょう。
確定フラグは \(O(\max A_i)\) 通り、本問の制約上では \(2^{60}\) 通りありうるので、愚直にこの方針を実装しては時間計算量も空間計算量も不十分です。

本当にこの方針は正解に繋がらないのでしょうか？

---

\(A\) の全要素の \({\rm OR}\) を \(o\) とした時に \(o\) にて \(1\) となる桁全てが確定した(すなわち、本来その桁は \(1\) になる可能性があったが、今や \(x\) の値を変えようがない)場合、そのような状態は直ちに排除すると取り決めます。 … ★
すると、操作を遡る各段階で、ありうる確定フラグ、さらに言うとありうる操作列の接尾辞は高々 \(2\) 種類であることが証明できます。

最初、確定フラグは \(0\) です。
遡っていくうち、 (b) と (c) により操作のどちらかが禁じられている場合は操作は分岐しません。
最初に確定フラグの分岐が発生する際、 (a) と (d) のみが発生していることになります。
このとき、確定フラグが残っている全ての桁が \(A_i\) と \(M\) とで一致し、以下の \(2\) 通りに分岐します。

• \(M\) にて \(0\) である桁のみに確定フラグが立っていない状態が残る。
  • これ以降 (a) と (b) しか発生せず、 (b) が発生した場合には分岐は発生しません。 (a) のみが発生し分岐した場合、分岐の片方は必ずもう \(x\) の値を変えようがない状態に陥っているため、取り決めにより分岐はないものだと見なしてよい。
• \(M\) にて \(1\) である桁のみに確定フラグが立っていない状態が残る。
  • 上記と同様の議論で示されます。

以上より、確定フラグ \(f\) を持って後ろから操作列を遡る方法でこの問題を \(O(N)\) で解く見通しが立ちました。

---

\((\) 確定フラグ, 操作 \(2\) の残り回数, 左 \(2\) つの状況に該当する場合の数 \()\) をひとつの状態として持って遡っていくことを考えます。初期状態は \((0,K,1)\) です。
これを DFS や BFS の要領で遡っていきます。
そして、確定フラグが★の取り決めに該当する状態になった場合、残りの操作の決め方は以下のような二項係数の和で表現されます。

• \(\displaystyle \sum_{i=0}^{a} \binom{b}{i}\)
  • ただし、 \(a\) は操作 \(2\) の残り回数、 \(b\) は操作自体の残り回数

これで、この問題を時間計算量 \(O(N^2)\) で解くことができました。
しかし、 \(O(N^2)\) ではまだ不十分です。どうすればよいでしょうか？

---

状態の \(3\) つ目の要素の初期値を \(1\) ではなく \(\displaystyle \sum_{i=0}^{K} \binom{N}{i}\) としておき、欲しい和を保持しながら遡ることができます。こうすることで、欲しい二項係数の和を \(O(1)\) で取得できるようになり、時間計算量 \(O(N)\) でこの問題に正解できます。
詳細な遷移式を立てるにあたって、パスカルの三角形をイメージすると考えやすいでしょう。
パスカルの三角形のある行のうち左からいくつかの要素の和を保持することになります。この状態を保ちながら、上の行へと昇っていきます。
遷移中に要求される操作は、 \(N\) を \(1\) 減らしつつ、 \(K\) を \(0\) あるいは \(1\) 減らすというものです。
実際に、 \(\displaystyle \sum_{i=0}^{K} \binom{N}{i}\) から \(\displaystyle \sum_{i=0}^{K} \binom{N-1}{i}\) を高速に求めてみましょう。
\(\displaystyle S_u=\sum_{i=0}^{K} \binom{N-1}{i}, S_d=\sum_{i=0}^{K} \binom{N}{i}\) とします。
パスカルの三角形を観察すると、 \(S_u\) にて足される各要素が \(S_d\) では概ね \(2\) 回加算されている状態になります。
但し、 \(\displaystyle \binom{N-1}{K}\) だけは \(S_d\) に加算される回数が \(1\) 回です。
以上より、 \(\displaystyle S_d = 2S_u - \displaystyle \binom{N-1}{K}\) という式が成り立ち、 \(S_d\) から \(S_u\) を時間計算量 \(O(1)\) で求めることができます。
\(K\) が \(1\) 減る場合も同様に時間計算量 \(O(1)\) で遡ることができます。

結局、全体で \(O(N \log{(\max A_i)})\) でこの問題に正解できます (bit演算を定数時間とみなして活用すると、本問題の制約下では時間計算量 \(O(N)\) で解けます)。
最初の操作まで遡ってなお確定フラグが立ちきっていない場合でも、 \(M\) にて \(1\) となる桁さえ確定していれば \(x=M\) を達成することに注意してください。

実装例 (C++):

#include<bits/stdc++.h>
#include<atcoder/all>

using namespace std;
using namespace atcoder;
using ll=long long;

const ll MXM=200005;

using mint = modint998244353;
vector<mint> fac(MXM),invfac(MXM);

void calc_fac(){
  fac[0]=mint(1);
  for(ll i=1;i<MXM;i++){
    fac[i]=fac[i-1]*mint(i);
  }
  invfac[MXM-1]=mint(1)/fac[MXM-1];
  for(ll i=MXM-2;i>=0;i--){
    invfac[i]=invfac[i+1]*mint(i+1);
  }
}

mint nCr(ll n,ll r){
  if(n<r){return 0;}
  return fac[n]*invfac[r]*invfac[n-r];
}

using tup=tuple<ll,ll,mint>;

int main(){
  ll al=(1ll<<60)-1;
  calc_fac();
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t;
  cin >> t;
  while(t--){
    ll n,k;
    cin >> n >> k;
    ll o=0;
    vector<ll> a(n);
    for(auto &nx : a){
      cin >> nx;
      o|=nx;
    }
    ll d1=0;
    for(ll i=n-k;i<n;i++){d1|=a[i];}
    ll d0=(al^d1);
    mint ini(0);
    for(ll i=0;i<=k;i++){ ini+=nCr(n,i); }
    vector<tup> sta={{0,k,ini}};
    mint res=0;
    for(ll i=n-1;i>=0;i--){
      {
        vector<tup> nsta;
        for(auto [f,rk,pat] : sta){
          ll e0=((al^f)&d0);
          ll e1=((al^f)&d1);
          int ban=0;
          if((e0&a[i])>0){ban|=2;}
          if((e1&(al^a[i]))>0){ban|=1;}
          if((ban&1)==0){
            // and
            mint npat=(pat+nCr(i,rk))/mint(2);
            nsta.push_back(tup{(f|(e0&(al^a[i]))),rk,npat});
          }
          if((ban&2)==0 && rk>0){
            // or
            mint npat=(pat-nCr(i,rk))/mint(2);
            nsta.push_back(tup{(f|(e1&a[i])),rk-1,npat});
          }
        }
        sta=nsta;
      }
      {
        vector<tup> nsta;
        for(auto [f,rk,pat] : sta){
          if((f&o)==o){
            res+=pat;
          }
          else{
            nsta.push_back(tup{f,rk,pat});
          }
        }
        sta=nsta;
      }
    }
    for(auto [f,rk,pat] : sta){
      if((f&d1)==d1){res+=pat;}
    }
    cout << res.val() << "\n";
  }
  return 0;
}