We can observe that "O" and "K" do not "interlock" with each other. So this problem is just finding two disjoint $$$4 \times 3$$$ sub-grids. Using brute force is enough.

Bonus: solve the problem when $$$n,m \le 10^3$$$.

#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n, m; cin >> n >> m;
    int ans = 0;
    for (int i = 0; i < n-3; i++) {
        for (int j = 0; j < m-2; j++) {
            for (int i2 = 0; i2 < n-3; i2++) {
                for (int j2 = 0; j2 < m-2; j2++) {
                    if (min(i, i2) + 3 < max(i, i2) || min(j, j2) + 2 < max(j, j2)) {
                        ans++;
                    }
                }
            }
        }
    }
    cout << ans << "\n";
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("file.in", "r", stdin)
    //freopen("file.out", "w", stdout);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

Note $$$k$$$ is the maximum integer such that $$$2^k \le n$$$. We can proof $$$a+b \le 2^(k+1)-1$$$.

Proof:since $$$a$$$ & $$$b=0$$$, there is no carry bit in $$$a+b$$$. And we can pick $$$a=2^{k}-1$$$ and $$$b=2^{k}$$$ to make $$$a+b=2^(k+1)-1$$$.

When $$$a+b=2^(k+1)-1$$$, we can see picking $$$a=2^{k}-1$$$ and $$$b=2^{k}$$$ makes $$$a \cdot b$$$ maximum. So the answer is $$$2^{k} \cdot (2^{k}-1)$$$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        ll val=0;
        for(ll i=0;i<31;i++){
            if((n&(1LL<<i))>0) val=i;
        }
        cout<<(1LL<<val)*((1LL<<val)-1)<<"\n";
    }
}

Note $$$k$$$ is the maximum integer such that $$$2^k \le n$$$. At first, we can easily see a lower bound of the answer — $$$2^{k-1}$$$. To reach this lower bound, we just pick $$$a=2^{k-1}$$$ and $$$b=2^k$$$.

Next, we only consider $$$a∈[2^{k-1}+1,2^{k}-1]$$$ and $$$b∈[2^k+1,2^k+2^{k-1}-1]$$$ which make $$$\gcd(a,b)>2^{k-1}$$$ possible.

We can see the following conclusions.

Conclution 1: $$$\gcd(a,b)=a$$$.

Proof 1: if $$$\gcd(a,b)<a$$$, it means $$$\gcd(a,b)\le a/2 <2^{k-1}$$$, which is too small.

Conclution 2: $$$b=2a$$$.

Proof 2: if $$$b=ka(k>2)$$$, it means $$$b>2^k+2^{k-1}$$$, which is too large.

Now, we need to find the maximum $$$a$$$ that satisfies $$$a$$$ & $$$2a=0$$$. This only holds when there are no two consecutive $$$1$$$'s in the binary representation of $$$a$$$. So, the answer is a number — the largest, not exceeding $$$n$$$, where there are no two consecutive $$$1$$$'s in binary representation.

#include <bits/stdc++.h>
#define all(s) s.begin(), s.end()

using namespace std;
using ll = long long;

const int _N = 1e5 + 5;

void solve() {
	ll n; cin >> n;
	ll x = 0;
	int lst = 0;
	for (ll bit = 29; bit >= 0; bit--) {
		if (x + (1 << bit) <= n && lst == 0) {
			lst = 1;
			x |= (1 << bit);
		} else lst = 0;
	}
	cout << x / 2 << '\n';
}

int main() {
	int T; cin >> T;
	while (T--) {
		solve();
	}
}

We can observe that the upper bound of the answer is $$$\frac{n(n+1)}{2}$$$(corresponding to $$$[0,1,...,n-1]$$$) and the lower bound is $$$n$$$(corresponding to $$$[n-1,n-2,...,1,0]$$$).

In fact, we construct the permutation for all $$$n \le S \le \frac{n(n+1)}{2}$$$. Note $$$x$$$ as the maximum number such that $$$x+(x+1)+(x+2)+...+n \ge S$$$, we have $$$S=y+(x+1)+(x+2)+...+n(y \le x)$$$.

• If $$$y \neq x$$$, we get $$$p=[1,...,y-1,y+1,...,0,y,x+1,x+2,...,n]$$$;

• Otherwise, we get $$$p=[1,2,...,...,x-1,0,x,x+1,x+2,...,n]$$$;

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        ll n,k;
        cin>>n>>k;
        if(k<n || k>(n*(n+1))/2) cout<<"-1\n";
        else{
            if(k==n){
                for(ll i=1;i<n;i++) cout<<i<<" ";
                cout<<0<<"\n";
            }
            else if(k==(n*(n+1))/2){
                for(ll i=0;i<n;i++) cout<<i<<" ";
                cout<<"\n";
            }
            else{
                k-=n;
                vector<ll> ans(n);
                ll val=0,ind=0,ind1=0;
                for(ll i=0;i<n;i++) ans[i]=i;
                for(ll i=n-1;i>0;i--){
                    if(k>i) k-=i;
                    else{
                        swap(ans[i-1],ans[0]);
                        val=k;
                        ind=i;
                        break;
                    }
                }
                for(ll i=0;i<n;i++){
                    if(ans[i]==val){
                        ind1=i;
                        break;
                    }
                }
                swap(ans[ind],ans[ind1]);
                for(auto i:ans) cout<<i<<" ";
                cout<<"\n";
            }
        }
    }
}

Reimagine the integers in $$$a$$$ as binary integers. Since XOR operation is done before any addition, this means that we can count the contribution of each bit separately, because XOR operation can be done by doing the XOR operation for each bit, and addition can also be done in a similar way.

Let $$$s_k$$$ be the sum of costs from all $$$2^{n-1}$$$ possible expressions if we only consider the $$$k$$$-th bit from each integer as the elements. Then, the sum of costs is $$$\sum_{i=0}^{28} s_i \cdot 2^i$$$.

Let's try to count $$$s_0$$$. We will use dynamic programming to solve this. Let $$$dp_i$$$ be the sum of costs from all $$$2^{i-1}$$$ possible expressions if we only consider the $$$0$$$-th bit from each integer as the elements, and we only consider the first $$$i$$$ elements. Let the $$$0$$$-th bit of $$$a_i$$$ be $$$b_i$$$. Then, $$$dp_0 = 0$$$ and $$$dp_i = \sum_{x=0}^{i-1} (dp_x + (b_{x+1} \oplus b_{x+2} \oplus \dots \oplus b_i))$$$. Although doing this naively would result in $$$O(n^3)$$$ transition, we can optimize this to $$$O(n)$$$ using prefix sum.

Let $$$pdp_i = \sum_{x=0}^{i} dp_x$$$ and $$$pb_i = b_1 \oplus b_2 \oplus \dots \oplus b_i$$$. Then, $$$dp_i = pdp_{i-1} + \sum_{x=0}^{i-1} (pb_x \oplus pb_i)$$$. Notice that the second expression is still $$$O(n)$$$. So, to count it in $$$O(1)$$$, we just have to store two extra variables $$$c_{i,0}$$$ and $$$c_{i,1}$$$, where $$$c_{i,k}$$$ is the number of integers $$$x$$$ such that $$$1 \leq x \leq i$$$ and $$$pb_x = k$$$. If $$$pb_i = 0$$$, the second expression is equal to $$$c_{i,1}$$$. Otherwise, the second expression is equal to $$$c_{i,0}$$$.

Other values of $$$s_i$$$ can be counted in a similar way.

Time complexity: $$$O(n \log a_i)$$$

// #pragma GCC optimize ("Ofast")
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pob pop_back
const int MOD = 1e9 + 7;
const int MODD = 998244353;
const int MAXN = 5e5 + 2;
const ll BIGG = 2e18;
 
using namespace std;
 
int a[MAXN];
ll dp[MAXN], cnt[2], pref[MAXN];
 
void solve() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    ll res = 0, comb;
    bool od;
    for (int i = 0; i < 29; i++) {
        od = true;
        cnt[0] = 0;
        cnt[1] = 1;
        comb = 1;
        if (a[0] % 2) {
            dp[0] = 1;
            pref[0] = 1;
            od = !od;
        }
        else {
            dp[0] = 0;
            pref[0] = 0;
        }
        a[0] >>= 1;
        cnt[od]++;
        for (int i = 1; i < n; i++) {
            comb = (comb * 2) % MODD;
            if (a[i] % 2) od = !od;
            a[i] >>= 1;
            dp[i] = (pref[i - 1] + cnt[!od]) % MODD;
            pref[i] = (pref[i - 1] + dp[i]) % MODD;
            cnt[od] = (cnt[od] + comb) % MODD;
        }
        res = (res + dp[n - 1] * (1 << i)) % MODD;
    }
    cout << res << endl;
}
 
int main(){
    // ios_base::sync_with_stdio(false), cin.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

Case $$$1$$$:If both $$$a_i=1$$$ and $$$b_j=0$$$ exist, the answer is $$$0$$$.

Case $$$2$$$:If $$$a_i=1$$$ exist and $$$b_j=1$$$ for all $$$j$$$, the answer is $$$(2^n-1)^k$$$, where $$$k$$$ is the number of $$$i$$$ satisfying $$$a_i=0$$$;

Case $$$3$$$:If $$$b_j=0$$$ exist and $$$a_i=0$$$ for all $$$i$$$, it is similar to case $$$2$$$.

Case $$$4$$$:If $$$a_i=0$$$ and $$$b_j=1$$$ for all $$$i,j$$$, we need to exclude all invalid cases. That is, the caces that there is at least one row containing all $$$1's$$$, or there is at least one coloum containing all $$$0's$$$. Using the Inclusion-Exclusion Principle, we get the answer is $$$2^{n^2}-2\Sigma^{n}_{i=1}((-1)^{i} \cdot C(n,i)·2^{n^2-i·n})$$$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);

ll mod=1e9+7;
 
long long power(long long a,long long b){
  long long x=1,y=a;
  while(b>0){
    if(b&1ll){
      x=(x*y)%mod;
    }
    y=(y*y)%mod;
    b>>=1;
  }
  return x%mod;
}
 
long long modular_inverse(long long n){
  return power(n,mod-2);
}
 
#define MAXN 2000005
 
long long factorial[MAXN];
long long invfact[MAXN];
 
void cfact(){
  long long i;
  factorial[0]=1;
  factorial[1]=1;
  for(i=2;i<MAXN;i++){
    factorial[i]=factorial[i-1]*i;
    factorial[i]%=mod;
  }
  invfact[MAXN-1]=modular_inverse(factorial[MAXN-1]);
  for(i=MAXN-2;i>=0;i--){
    invfact[i]=invfact[i+1]*(i+1);
    invfact[i]%=mod;
  }
}
 
long long calcnCr(long long n,long long k){
  if(k<0 || n<k){return 0;}
  return (factorial[n]*((invfact[k]*invfact[n-k])%mod))%mod;
}

int main(){
    fast;
    cfact();
    ll t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        string s1,s2;
        cin>>s1>>s2;
        ll cnt11=count(s1.begin(),s1.end(),'1');
        ll cnt20=count(s2.begin(),s2.end(),'0');
        if(cnt11>0 && cnt20>0) cout<<"0\n";
        else if(cnt11==0 && cnt20>0) cout<<power((power(2,n)-1)%mod,n-cnt20)%mod<<"\n";
        else if(cnt11>0 && cnt20==0) cout<<power((power(2,n)-1)%mod,n-cnt11)%mod<<"\n";
        else{
            ll res=0;
            for(ll i=0;i<n;i++){
                if(i%2==0){
                    res=(res-((calcnCr(n,i+1))*power(2,n*n-(i+1)*n))%mod+mod)%mod;
                }
                else{
                    res=(res+((calcnCr(n,i+1))*power(2,n*n-(i+1)*n))%mod)%mod;
                }
            }
            cout<<(power(2,n*n)+2*res)%mod<<"\n";
        }
    }
}

Use a variant of the Euler tour. Let's call it BFS-children-first-DFS.

First, node $$$1$$$ is added to the sequence, then $$$\DFS(1)$$$ is performed. When $$$DFS(x)$$$ is called, all child nodes of $$$x$$$ are added to the sequence, and then $$$\DFS(son[x][i])$$$ is performed.

For example, for the tree shown above, the BFS-children-first-DFS order is $$$[1,2,11,3,4,5,6,7,8,10,9]$$$.

In this way, the subtree rooted at node $$$x$$$ (excluding $$$x$$$ itself) and all the child nodes of node $$$x$$$ are within a contiguous segment of the sequence. This makes it easy to maintain the operations in $$$O(n log n)$$$.

#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef long double ld;

const ll P = 1e18;
const ld phi=1.61803398874989;
const ll a=1134903170, b=0, c=1836311903;

//code for euclidean algo from blog mentioned in the editorial

struct Node {
    ll x, y, sumx, sumy;
    Node() : x(0), y(0), sumx(0), sumy(0) {}
    Node operator*(Node b) {
        Node a = *this, c;
        c.x = (a.x + b.x) % P;
        c.y = (a.y + b.y) % P;
        c.sumx = (a.sumx + b.sumx + a.x * b.x) % P;
        c.sumy = (a.sumy + b.sumy + a.y * b.x) % P;
        return c;
    }
};
Node pow(Node a, ll b) {
    Node ans;
    while (b) {
        if (b & 1ll) ans = ans * a;
        a = a * a;
        b >>= 1ll;
    }
    return ans;
}
Node euclid(ll p, ll q, ll r, ll n, Node U, Node R) {
    if (!n) return Node();
    if (r >= q) return pow(U, r / q) * euclid(p, q, r % q, n, U, R);
    if (p >= q) return euclid(p % q, q, r, n, U, pow(U, p / q) * R);
    ll m = (1ll * p * n + r) / q;
    if (!m) return pow(R, n);
    return pow(R, (q - r - 1) / p) * U * euclid(q, p, (q - r - 1) % p, m - 1, R, U) * pow(R, n - (q * m - r - 1) / p);
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    Node U, R;
    U.y = 1, R.x = 1, R.sumx = 1;
    int t;cin>>t;while (t--){
    ll l, r;cin>>l>>r;
    ll sp=ceil(phi*l);
    ll fa=(r-l+1)%P;
    if (sp<=r){
    ll ne=r-sp+1;
    fa=(fa-((ne*(l-1))%P)+4*P)%P;
    auto ans_r = euclid(a, c, b, r, U, R);
        ans_r.sumy = (ans_r.sumy + (b / c)) % P;
        auto ans_sp = euclid(a, c, b, sp-1, U, R);
        ans_sp.sumy = (ans_sp.sumy + (b / c)) % P;
        fa=(fa+ans_r.sumy-ans_sp.sumy+5*P)%P;
    }
    cout<<fa<<endl;
    }
    return 0;
}