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 minimum integer such that $$$2^k>n$$$. We can proof $$$a+b< \le 2^k-1$$$.

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

When $$$a+b=2^k-1$$$,we can see picking $$$a=2^{k-1}-1$$$ and $$$b=2^{k-1}$$$ is optimal. So the answer is $$$2^{k-1} \cdot (2^{k-1}-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";
    }
}

Root the tree at a node, say $$$1$$$. Now, calculate depths of all nodes from the root, and mark all nodes with even depth as $$$0$$$, and odd depth as $$$1$$$. Imagine we connect two nodes of the different parity. This would form a cycle of even length and so the diametrically opposite vertices on the cycle would violate the condition.

So, we are left with choices where we connect vertices of the same parity. This will always satisfy our conditions.

This is because precisely $$$1$$$ cycle is formed, with trees dangling to it. For 2 vertices on the cycle, there are never 2 shortest paths since total cycle length is odd. The trees hanging to the cycle trivially satisfy the condition.

Also since the path between two attached trees also goes through the cycle, it essentially reduces to shortest path between corresponding points on the cycle and is also unique.

So our answer is all pairs of nodes having the same parity. Complexity is $$$O(n)$$$.

#include<bits/stdc++.h>
#define pi 3.14159265358979323846
#define eb emplace_back
#define ll long long
#define w(t) while(t--)
#define F first
#define S second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define iofast ios::sync_with_stdio(0);cin.tie(0);
using namespace std;
//give sin(),cos() radian, and asin(),acos() gives you radian
vector<int> v[1000010];
bool ch[1000010];
ll cnt1,cnt0;
void DFS(int po,bool c){
	if(!c) cnt0++;
	else cnt1++;
	ch[po]=1;
	for(auto i:v[po]){
		if(!ch[i]){
			DFS(i,!c);
		}
	}
	return;
}
void solve(){
	int n,a,b;
	cnt1=0;
	cnt0=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		v[i].clear();
		ch[i]=0;
	}
	for(int i=1;i<n;i++){
		cin>>a>>b;
		v[a].eb(b);
		v[b].eb(a);
	}
	DFS(1,0);
	cout<<(((cnt1-1)*cnt1)/2)+(((cnt0-1)*cnt0)/2)<<'\n';
	return;
}
int main(){
	iofast
	int t;
	cin>>t;
	w(t) solve();
	return 0;
}

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";
        }
    }
}

WLOG, assume that $$$x \geq y$$$. We desire for Alice to win. Let us check the scenarios where this is possible:

Case 1: $$$(x \geq 2y)$$$: This means Alice has to subtract a multiple of $$$y$$$ from $$$x$$$. There are, say $$$k$$$ choices of subtracting $$$y, 2y, .., ky$$$. We have more than $$$1$$$ choices $$$(k>1)$$$. If $$$ky$$$ is winning, Alice chooses that. If it is losing, then since $$$k>1$$$, Alice can choose $$$(k-1)y$$$ and Bob will then be forces to subtract $$$y$$$ in the next move, essentially making Bob choose the losing $$$ky$$$ state. So Alice always wins.

Case 2: $$$(x<2y)$$$: This means there is only one possible move, which is to subtract $$$y$$$ from $$$x$$$. If the resulting pair of numbers $$$(y,x-y)$$$ is losing, Alice wins. Else she loses.

Now, for her to loose, like in case 1, $$$(y \geq 2(x-y))$$$ (we already know $$$y$$$ is larger than $$$(x-y)$$$ since $$$x<2y$$$). So for her to win, $$$y \leq 2(x-y)$$$, which means $$$x \geq \frac{3y}{2}$$$.

If $$$y<2(x-y)$$$, we again subtract and go to the next iteration. The new pair is $$$(x-y,2y-x)$$$. For it the winning conditions come out to be $$$x \geq \frac{5y}{3}$$$.

If we keep doing the iterations, we observe that in the $$$n^{th}$$$ step the condition comes out to be $$$x \geq \frac{F(n+1)}{F(n)}$$$ where $$$F(n)$$$ is the $$$n^{th}$$$ Fibonacci number $$$(F(1)=1, F(2)=2)$$$. So, to get the exact bound, we take its limit as $$$n$$$ approaches infinity, and get $$$\lim_{n \to \infty} \frac{F(n+1)}{F(n)} = \frac{1+\sqrt{5}}{2} = \phi$$$. So Alice wins iff $$$(x> \phi y)$$$ (equality dropped since both $$$x$$$ and $$$y$$$ are integers).

So our problem becomes counting the number of $$$(l,r)$$$ such that $$$r> \phi l$$$. Since our numbers $$$\leq 10^9$$$, we can take an appropriate approximation of $$$\phi$$$, (say $$$\frac{p}{q}$$$).

For approximation you can use the fibonacci numbers just bigger than $$$10^9$$$. They match $$$\phi$$$ upto $$$14$$$ decimal places and works fine for our purpose.

Now our problem boils down to calculating $$$\sum_{x=L'}^{R} \lfloor \frac{xq}{p} \rfloor$$$ (here $$$L'$$$ is the first index such that $$$\lfloor \frac{L'q}{p} \rfloor \geq L $$$).

This is a standard problem and can be calculated in $$$O(log(max(p,q))$$$ complexity. Here is reference a blog with exact details about solving this: https://www.cnblogs.com/apjifengc/p/17492207.html

#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;
}