#include<bits/stdc++.h>
using namespace std;
int main()
{
    int test,a,b,n;
    cin>>test;
    while(test--){
        cin>>a>>b>>n;
        switch (n%3){
            case 0:
              cout<<a<<endl;
              break;
            case 1:
              cout<<b<<endl;
              break;
            default:
              cout<<(a^b)<<endl;
        }
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 2e3 + 5;
int a[N];

int main(){
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; ++i){
        scanf("%d", &a[i]);
    }

    int ans = n - 1;
    map<int, int> freq; 
    for(int i = 0; i < n; ++i){
        bool validPrefix = true;
        for(int j = 0; j < i; ++j){
            freq[a[j]]++;
            if(freq[a[j]] == 2){
                validPrefix = false;
                break;
            }
        }
        int min_index_suffix = n;
        for(int j = n - 1; j >= i; --j){
            freq[a[j]]++;
            if(freq[a[j]] == 1){
                min_index_suffix = j;
            }
            else break;
        }
        if(validPrefix){
            ans = min(ans, min_index_suffix - i);
        }
        
        freq.clear();
    }
    cout << ans << '\n';

Try to solve this problen in $$$O(n \cdot log(n))$$$

#include <bits/stdc++.h>
using namespace std;
#define int     long long
#define ld      long double
#define pii     pair<int ,int>
#define pld     pair<ld ,ld>
#define F       first
#define S       second
#define mod     1000000007
#define pb      push_back
#define mp      make_pair
#define all(x)  x.begin(),x.end()
#define mset(x) memset(x, 0, sizeof(x));
#define ios     ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = 1000;

int n, grid[N][N];
void run(){
    cin >> n;

    /* 
    Divide Grid into Quandrants as follows:
    1 | 2
    -----
    3 | 4
    */

    int fill = 0;
    for(int i = 0; i < n/2; i++){
        for(int j = 0; j < n/2; j++){

            grid[i][j]              = 4*fill + 1;   // 1st quadrant
            grid[i][j + n/2]        = 4*fill + 2;   // 2nd quadrant
            grid[i + n/2][j]        = 4*fill + 3;   // 3rd quadrant
            grid[i + n/2][j + n/2]  = 4*fill;       // 4th quadrant
            
            fill++;

        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cout << grid[i][j] << " ";
        }
        cout << endl;
    }
}

signed main(){
    int tests = 1;
    // cin >> tests;
    for(int i = 1; i <= tests; i++) run();
    return 0;
}

#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>

using namespace std;

typedef long long ll;

const ll INF = 1e16 + 239;
const int MAXN = 1e6 + 239;

ll a[MAXN];

namespace SegmentTree {
	int n;
	ll t[4 * MAXN];
	ll mod[4 * MAXN];

	void pull(int v) {
		t[v] = min(t[2 * v + 1], t[2 * v + 2]);
	}

	void apply(int v, ll val) {
		t[v] += val;
		mod[v] += val;
	}

	void push(int v) {
		if (mod[v] != 0) {
			apply(2 * v + 1, mod[v]);
			apply(2 * v + 2, mod[v]);
			mod[v] = 0;
		}
	}

	void build(int v, int l, int r) {
		if (l + 1 == r) {
			t[v] = a[l];
		} else {
			int m = (r + l) >> 1;
			build(2 * v + 1, l, m);
			build(2 * v + 2, m, r);
			pull(v);
		}
	}

	void add(int v, int l, int r, int ql, int qr, ll val) {
		if (r <= ql || qr <= l) {
			return;
		} else if (ql <= l && r <= qr) {
			apply(v, val);
		} else {
			push(v);
			int m = (r + l) >> 1;
			add(2 * v + 1, l, m, ql, qr, val);
			add(2 * v + 2, m, r, ql, qr, val);
			pull(v);
		}
	}

	int go_down(int v, int l, int r) {
		if (l + 1 == r) {
			return l;
		} else {
			push(v);
			int m = (r + l) >> 1;
			int res = -1;
			if (t[2 * v + 2] == 0) {
				res = go_down(2 * v + 2, m, r);
			} else {
				res = go_down(2 * v + 1, l, m);
			}
			pull(v);
			return res;
		}
	}

	void init(int n_) {
		n = n_;
		build(0, 0, n);
	}

	void add(int l, int r, ll val) {
		add(0, 0, n, l, r, val);
	}

	void add(int pos, ll val) {
		add(0, 0, n, pos, pos + 1, val);
	}

	int last_zero() {
		return go_down(0, 0, n);
	}
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	SegmentTree::init(n);
	vector<int> ans(n, -1);
	for (int i = 1; i <= n; i++) {
		int pos = SegmentTree::last_zero();
		ans[pos] = i;
		SegmentTree::add(pos, INF);
		SegmentTree::add(pos + 1, n, -i);
	}
	for (auto t : ans) {
		cout << t << ' ';
	}
	cout << endl;
}

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

const int N = 2e5 + 5;
long long BIT[N], s[N];
int n;
int ans[N];

void update(int x, int delta){
      for(; x <= n; x += x&-x)
        BIT[x] += delta;
}

long long query(int x){
     long long sum = 0;
     for(; x > 0; x -= x&-x)
        sum += BIT[x];
     return sum;
}

int searchNumber(long long prefSum){

    int num = 0;
    long long sum = 0;
    for(int i = 21; i>=0 ; --i){
        if((num + (1<<i) <= n) && (sum + BIT[num + (1<<i)] <= prefSum)){
            num += (1<<i);
            sum += BIT[num];
        }
    }
    return num + 1;
}

int main(){
	scanf("%d",&n);
	for(int i = 1; i <= n; ++i){
        update(i, i);
		scanf("%lld", &s[i]);
	}
	for(int i = n; i >= 1; --i){
        ans[i] = searchNumber(s[i]);
        update(ans[i], -ans[i]);
    } 
    for(int i = 1; i <= n; ++i){
        printf("%d", ans[i]);
        if(i < n){
            printf(" ");
        }
        else printf("\n");
    }
}

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

const int N = 1e6 + 5;
long long ans[N];
vector<pair<int, int> > add_element[N], remove_element[N];
multiset<int> global_ms[N];

int main(){
	int n,w;
	scanf("%d %d", &n, &w);
	for(int i = 0; i < n; ++i){
		int cnt;
		scanf("%d", &cnt);
		for(int j = 0; j < cnt; ++j){
			int x,l,r;
			scanf("%d", &x);
			add_element[j].push_back(make_pair(x, i));
			remove_element[j + w - cnt].push_back(make_pair(x, i));
		}
		if(cnt < w){
			add_element[cnt].push_back(make_pair(0, i));
			remove_element[w - 1].push_back(make_pair(0, i));
			add_element[0].push_back(make_pair(0, i));
			remove_element[w - 1 - cnt].push_back(make_pair(0, i));
		}
	}
	for(int i = 0; i < w; ++i){

		for(auto j:add_element[i]){
			int idx = j.second;
			int val = j.first;
			ans[i] -= (global_ms[idx].empty()? 0: *global_ms[idx].rbegin());
			global_ms[idx].insert(val);
			ans[i] += *global_ms[idx].rbegin();
		}	

		if(i < w - 1){
			ans[i + 1] = ans[i];
			for(auto j:remove_element[i]){
				int idx = j.second;
				int val = j.first;
				ans[i + 1] -= (*global_ms[idx].rbegin());
				global_ms[idx].erase(global_ms[idx].find(val));
				ans[i + 1] += (global_ms[idx].empty()? 0: *global_ms[idx].rbegin());
			}
		}
		printf("%lld ",ans[i]);
	}
	printf("\n");
}

#include <bits/stdc++.h>

#define ll          long long
#define pb          push_back
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define x           first
#define y           second
#define sz(x)       (int)x.size()
#define endl        '\n'
#define hell        1000000007
#define rep(i,a,b)  for(int i=a;i<b;i++)
using namespace std;

int n,a[1000006],ans,bits;
pii dp[1<<21];

void add(int mask,int w){
    if(dp[mask].x==-1) dp[mask].x=w;
    else if(dp[mask].y==-1){
        if(dp[mask].x==w) return;
        dp[mask].y=w;
        if(dp[mask].x>dp[mask].y) swap(dp[mask].x,dp[mask].y);
    }
    else{
        if(dp[mask].y<w){
            dp[mask].x=dp[mask].y;
            dp[mask].y=w;
        }
        else if(dp[mask].x<w and dp[mask].y!=w) dp[mask].x=w;
    }
}


void merge(int m1,int m2){
    if(dp[m2].x!=-1) add(m1,dp[m2].x);
    if(dp[m2].y!=-1) add(m1,dp[m2].y);
}

void solve(){
	memset(dp,-1,sizeof dp);
    cin>>n;
    rep(i,0,n){
        cin>>a[i];
        add(a[i],i);
        bits=max((int)log2(a[i]),bits);
    }
    bits++;
    rep(i,0,bits){
        rep(mask,0,1<<bits){
            if(mask&(1<<i)){
                merge(mask^(1<<i),mask);
            }
        }
    }
    rep(i,0,n){
        int cur=(1<<bits)-1-a[i];
        int opt=0;
        for(int j=bits-1;j>=0;j--){
            if((cur>>j)&1){
                if(dp[opt^(1<<j)].y!=-1 and dp[opt^(1<<j)].x>i){
                    opt^=(1<<j);
                }
            }
        }
        if(dp[opt].y!=-1 and dp[opt].x>i) ans=max(ans,a[i]^opt);
    }
    cout<<ans<<endl;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int phi[1000006];
void process_phis(int n){
    iota(phi,phi+n+1,0);
    for(int i = 2 ; i<=n;i++){
        if(phi[i]==i){
            phi[i]=i-1;
            for(int j=2*i;j<=n;j+=i){
                phi[j]=(phi[j]/i)*(i-1);
            }
        }
    }
}
int main(){
    int n,k;
    cin>>n>>k;
    if(k==1){
        cout<<3<<endl;
        return 0;
    }
    process_phis(n);
    k+=2;
    sort(phi+1,phi+n+1);
    cout<<accumulate(phi+1,phi+k+1,0LL)<<endl;
    return 0;
}

/**
 * This line was copied from template
 * This is nk_sqrt_300.cpp
 * 
 * @author: Nikolay Kalinin
 * @date: Fri, 23 Aug 2019 22:28:23 +0300
 */
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
    #define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
    #define eprintf(...) 42
#endif

using ll = long long;
using ld = long double;
using D = double;
using uint = unsigned int;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second

const int maxn = 100005;
const int infk = maxn;

const int BSZ = 700;

vector<int> gr[maxn];
vector<int> dead_ends[maxn];
int th[maxn][2];
int threshold[maxn];
int up[maxn], fastup[maxn];
bool isleaf[maxn];
int curcnt[maxn];
int was[maxn];
int curk, curkid;
int n;
int timer;
int c[maxn];
bool isinteresting[maxn];
vector<int> interesting;
pair2<int> qs[BSZ];
vector<int> at[2 * BSZ];
queue<int> q;
int path[maxn];
vector<int> ks;
vector<int> cntdead[2 * BSZ];
int intid[maxn];
vector<int> order;
int newid[maxn];
vector<int> grinit[maxn];
int compk[2 * infk + 5];

void leavedesc(int cur, int pr)
{
    newid[cur] = order.size();
    up[newid[cur]] = newid[pr];
    order.pb(cur);
    for (int i = 0; i < (int)grinit[cur].size(); i++)
    {
        if (grinit[cur][i] == pr)
        {
            swap(grinit[cur][i], grinit[cur].back());
            grinit[cur].pop_back();
            i--;
        } else
        {
            leavedesc(grinit[cur][i], cur);
        }
    }
}


inline void computecolor(int cur)
{
    if (was[cur] != timer) curcnt[cur] = 0;
    int cntred = curcnt[cur];
    cntred += (int)cntdead[intid[cur]].size() <= curkid ? cntdead[intid[cur]].back() : cntdead[intid[cur]][curkid];
    int cntblue = (int)gr[cur].size() - cntred;
    if (cntblue - cntred >= curk) c[cur] = 1;
    else c[cur] = 0;
}

inline void pushtoparent(int cur)
{
    if (cur == 0) return;
    int par = fastup[cur];
    
    int colorup = 1 - (curk >= th[cur][c[cur]]);
    
    if (was[par] != timer)
    {
        was[par] = timer;
        curcnt[par] = 0;
    }
    curcnt[par] += 1 - colorup;
}

int main()
{
    scanf("%d%d", &n, &curk);
    for (int i = 0; i < n - 1; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        u--, v--;
        grinit[u].pb(v);
        grinit[v].pb(u);
    }
    leavedesc(0, -1);
    
    for (int i = 0; i < n; i++)
    {
        for (auto t : grinit[i]) gr[newid[i]].pb(newid[t]);
    }
    
    for (int i = 0; i < n; i++) scanf("%d", &c[newid[i]]);
        
    for (int i = 0; i < n; i++) if (c[i] != -1) isleaf[i] = true;
    int nq;
    scanf("%d", &nq);
    for (int lq = 0; lq < nq; lq += BSZ)
    {
        int rq = min(nq, lq + BSZ);
        memset(isinteresting, 0, sizeof isinteresting);
        ks.clear();
        ks.pb(curk);
        for (int q = lq; q < rq; q++)
        {
            int t;
            scanf("%d", &t);
            if (t == 1)
            {
                int v;
                scanf("%d", &v);
                v--;
                v = newid[v];
                isinteresting[v] = true;
                qs[q - lq] = {v, -1};
            } else if (t == 2)
            {
                int v, newc;
                scanf("%d%d", &v, &newc);
                v--;
                v = newid[v];
                isinteresting[v] = true;
                qs[q - lq] = {v, newc};
            } else
            {
                int newk;
                scanf("%d", &newk);
                qs[q - lq] = {-1, newk};
                ks.pb(newk);
            }
        }
        
        sort(all(ks));
        ks.resize(unique(all(ks)) - ks.begin());
        int kssz = ks.size();
        ks.pb(infk);
        int curcompkid = 0;
        for (int i = -infk; i <= infk; i++)
        {
            compk[i + infk] = curcompkid;
            if (curcompkid < kssz && ks[curcompkid] == i) curcompkid++;
        }


        isinteresting[0] = true;
        interesting.clear();

        for (int i = 0; i <= kssz; i++) at[i].clear();

        for (int cur = 0; cur < n; cur++)
        {
            dead_ends[cur].clear();
            path[cur] = -1;
            if (isinteresting[cur])
            {
                path[cur] = -2;
            }
        }

        for (int cur = n - 1; cur >= 0; cur--)
        {
            int ret = -1;
            if (isinteresting[cur])
            {
                intid[cur] = interesting.size();
                interesting.pb(cur);
                cntdead[intid[cur]].clear();
                cntdead[intid[cur]].pb(0);
            }
            if (path[cur] == -1)
            {
                if (isleaf[cur])
                {
                    if (c[cur] == 0) at[compk[-infk + infk]].pb(cur);
                    else at[compk[infk + infk]].pb(cur);
                } else
                {
                    curcnt[cur] = 0;
                    int cntred = 0;
                    int cntblue = gr[cur].size();
                    at[compk[cntblue - cntred + 1 + infk]].pb(cur);
                }
            } else if (path[cur] == -2)
            {
                ret = cur;
            } else
            {
                ret = path[cur];
            }
            if (cur == 0) break;
            if (ret == -1) continue;
            
            if (path[up[cur]] == -1) path[up[cur]] = ret;
            else if (path[up[cur]] >= 0)
            {
                isinteresting[up[cur]] = true;
                fastup[path[up[cur]]] = up[cur];
                fastup[ret] = up[cur];
                path[up[cur]] = -2;
            } else
            {
                fastup[ret] = up[cur];
            }
        }
        
        timer++;
        for (int i = 0; i <= kssz; i++)
        {
            for (auto t : at[i]) q.push(t);
            while (!q.empty())
            {
                int cur = q.front();
                q.pop();
                if (was[cur] == timer) continue;
                was[cur] = timer;
                if (path[up[cur]] == -1)
                {
                    curcnt[up[cur]]++;
                    int cntred = curcnt[up[cur]];
                    int cntblue = gr[up[cur]].size() - cntred;
                    if (cntblue - cntred + 1 <= ks[i]) q.push(up[cur]);
                    else at[compk[cntblue - cntred + 1 + infk]].pb(up[cur]);
                } else if (path[up[cur]] == -2)
                {
                    int id = intid[up[cur]];
                    while ((int)cntdead[id].size() <= i) cntdead[id].pb(cntdead[id].back());
                    cntdead[id].back()++;
                } else { // in path
                    dead_ends[up[cur]].pb(ks[i]);
                }
            }
        }
        
        for (int cur = n - 1; cur >= 0; cur--) if (path[cur] != -1)
        {
            int cntchildren = gr[cur].size();
            if (path[cur] == -2)
            {
                th[cur][0] = -infk;
                th[cur][1] = +infk;
            } else
            {
                th[cur][0] = cntchildren + 1;
                th[cur][1] = cntchildren + 1;
                th[cur][0] = min(th[cur][0], max(th[path[cur]][0], cntchildren - 1 - 1 + 1));
                th[cur][1] = min(th[cur][1], max(th[path[cur]][1], cntchildren - 1 - 1 + 1));
                for (int i = 0; i < (int)dead_ends[cur].size(); i++)
                {
                    int cntred = i + 1;
                    int cntblue = cntchildren - cntred;
                    th[cur][0] = min(th[cur][0], max(dead_ends[cur][i], cntblue - cntred + 1));
                    th[cur][1] = min(th[cur][1], max(dead_ends[cur][i], cntblue - cntred + 1));
        
                    cntred = i + 1 + 1;
                    cntblue = cntchildren - cntred;
                    th[cur][0] = min(th[cur][0], max(max(th[path[cur]][0], dead_ends[cur][i]), cntblue - cntred + 1));
                    th[cur][1] = min(th[cur][1], max(max(th[path[cur]][1], dead_ends[cur][i]), cntblue - cntred + 1));
                }
                th[path[cur]][0] = th[cur][0];
                th[path[cur]][1] = th[cur][1];
            }
        }
        
        
        ::curkid = lower_bound(all(ks), curk) - ks.begin();
        for (int q = 0; q < rq - lq; q++)
        {
            timer++;
            if (qs[q].fi == -1)
            {
                curk = qs[q].se;
                ::curkid = lower_bound(all(ks), curk) - ks.begin();
            } else if (qs[q].se != -1) c[qs[q].fi] = qs[q].se;
            else
            {
                for (auto v : interesting)
                {
                    if (!isleaf[v]) computecolor(v);
                    pushtoparent(v);
                }
                printf("%d\n", c[qs[q].fi]);
            }
        }
    }
    return 0;
}

The answer array has to have N elements and K distinct elements.

Thus, choose K distinct elements to be from 1 to K and remaining N - K elements to be 1.

The sum of which is : (K * (K + 1) / 2) + N - K

Let P[i] be the difference between the number of days Bob studied and the number of days he didn't till ith day.

Thus, we have to ensure that P[i] >  = 0 for 1 <  = i <  = N.

Iterate over all i and greedily flip 0 to 1 whenever P[i] becomes negative.

Let us consider an array of N elements b, consisting of 0 and 1, 0 denotes Snorlax doesn't work out on the ith day and 1 indicates that he does.

The window size is K.

Let us look at the ith window, when you slide one window further, from the subarray sum, we have to subtract b[i] and add b[i + k]. Effectively adding b[i + k] - b[i]. If this value is 1, we can surely say that b[i] is 0 and b[i + k] is 1 and if this value  - 1, the reverse is true.

If this difference is 0, we can say that b[i] and b[i + k] are equal but can't tell the exact values.

If the absolute value of this difference is more than 1, array construction is impossible.

Note that, we thus get relations between b[i], b[i + k], b[i + 2k]... and so on. We just check if these relations are consistent. If we just know any of this group, we can figure out the rest of this group. Note that part of a group are those indices who have same remainder on division with l.

At an index, we cannot get more than 1 invalid value. Meaning, we can't say that b[i] is neither 0 nor 1.

There is still one constraint we haven't enforced yet and this is the sum of the values in 1st window, till now, we only looked the difference between consecutive windows.

We enforce this constraint by making 1 those values that are unknown and occur at the end of the 1st window (the end because we have to minimise the number of 1's too and the ending values have the largest remainders, it can easily be seen that those with large remainder occur fewer times than those with smaller remainder).

If we are unable to enforce the above constraint, then also making the array is impossible.

The complexity is O(N).

Let us first represent each cell with a number by 2^d[i][j]. For a grid to be palindrome, the xor of all values should have at max 1 set bit in it. For a grid to be divisible by 6, the sum of digits should be divisible by 3 and the grid should contain at least 2 even digits.

A corner case is when the grid consists of only a single element. [6] is the only single element grid possible.

Since, N * M <  = 100000, min(N, M) <  = 320 Lets suppose N <  = M, otherwise we can flip the grid diagonally and answer wont change. Lets iterate over 2 rows i and j. Let us store prefix_sums, prefix_xors and prefix_even_nos for the columns considering all rows from i to j. Let us iterate over the rightmost column k.

Now, all l's such that

• 

• 

• (pre_even[k] - pre_even[l - 1]) >  = 2

are valid leftmost columns of the grid.

For the third condition we can use 2 pointers. For first and second conditions, we can store frequency of xors along with in a [1«10][3] array and run an extra 9 size loop for second condition.

So, overall complexity will be O(min(N, M) * N * M * 10). Refer to the code for better understanding.

#include <bits/stdc++.h>

#define int         long long
#define pb          push_back
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define x           first
#define y           second
#define sz(x)       (int)x.size()
#define endl        '\n'
#define hell        1000000007
#define rep(i,a,b)  for(int i=a;i<b;i++)
using namespace std;
int n,m;
int ans;
vector<string> s;
vector<vi> colsum,colxor,coleven;
int prexor[1<<10][3],curxor[100005],cursum[100005],cureven[100005];
void solve(){
	cin>>n>>m;
	s.resize(n+1);
	rep(i,1,n+1){
		cin>>s[i];
		s[i]='#'+s[i];
	}
	if(n>m){
		rep(i,1,n+1) s[i].resize(n+1);
		rep(i,1,n+1){
			rep(j,i,n+1){
				swap(s[i][j],s[j][i]);
			}
		}
		swap(n,m);
	}
	colsum.resize(m+1);
	colxor.resize(m+1);
	coleven.resize(m+1);
	rep(i,1,m+1){
		colsum[i].resize(n+1);
		colxor[i].resize(n+1);
		coleven[i].resize(n+1);
		rep(j,1,n+1){
			colsum[i][j]=(colsum[i][j-1]+s[j][i]-'0')%3;
			colxor[i][j]=(colxor[i][j-1]^(1<<(s[j][i]-'0')));
			coleven[i][j]=coleven[i][j-1]+((s[j][i]-'0')%2==0);
		}
	}
	rep(i,1,n+1){
		rep(j,i,n+1){
			for(int k=0;k<(1<<10);k+=2) prexor[k][0]=prexor[k][1]=prexor[k][2]=0;
			rep(k,1,m+1) curxor[k]=curxor[k-1]^colxor[k][j]^colxor[k][i-1];
			rep(k,1,m+1) cursum[k]=(cursum[k-1]+colsum[k][j]-colsum[k][i-1]+3)%3;
			rep(k,1,m+1) cureven[k]=cureven[k-1]+coleven[k][j]-coleven[k][i-1];
			int lo=0;
			rep(k,1,m+1){
				while(lo<k and cureven[k]-cureven[lo]>=2){
					prexor[curxor[lo]][cursum[lo]]++;
					lo++;
				}
				ans+=prexor[curxor[k]][cursum[k]];
				rep(l,1,10) ans+=prexor[curxor[k]^(1<<l)][cursum[k]];
			}
		}
	}
	rep(i,1,n+1){
		rep(j,1,m+1){
			if(s[i][j]=='6'){
				ans++;
			}
		}
	}
	cout<<ans<<endl;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t=1;
    // cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

There are different ways to solve this problem. One is using a square-root trick as follows:

Run binary search over the maximum weight used. To check if a given maximum weight is valid we need to find the sum of weights from U to V with weight less than a given weight. This can be done by breaking the path in three parts : U to root, V to root and LCA(u, v) to root.

sum(U, V, W) = sum(U, root, W) + sum(V, root, W) - 2 * sum(lca, root, W) + (w[lca] < W) * w[lca]

So, we want to find the sum of weights less than W on a path from a node U to root.

Let’s divide the tree into blocks of size B and mark n / B special nodes such that any path from a node to root does not take more than B nodes until it reaches a special node.

One can do this by keeping a count of and then taking the index corresponding to the minimum value as base_height.

All nodes at a height h with will be marked special. Hence there can be at most n / B special nodes (pigeonhole principle) and distance between a node to its closest special node is less than B.

For each special node, store the weights in the path from root to this node in a sorted order. This can be done in a single dfs. This step will take W * (n / B) time if we sort the weights using counting sort (since the weights are bounded) where W is the upper bound for weight of nodes.

Then we can find the sum by moving up the tree until we reach a special node. For a special node, we can easily answer the query in log(n) using another binary search (upperbound/lowerbound). This step will take B + log(n) time per query.

Count of nodes can also be calculated along with the sum. We need to carefully handle the number of times nodes with maximum weight are used.

Overall time complexity is O(W * (n / B) + q * log(W) * (B + log(n))). An optimal value for B is close to 200.

Another solution is using persistent segment trees by keeping the information of root to a node in segment tree.

Refer this comment by Ashishgup.

The maximum length of G can be K. For length  >  = K + 1 , all elements of G won't be distinct.

The second condition can be expressed as

Lets make a directed graph containing K vertices from 0 to K - 1. An edge from X to Y signifies that in the sequence G, Y can come after X.

For checking if Y can come after X, we have: , for some A.

There exists some A if gcd(X, K) divides Y. This can also be written as gcd(X, K) divides gcd(Y, K). (Note that there can be multiple values of A but we have to find number of sequences for G and not for F, so it doesn't matter.)

Now, our task is to calculate the number of simple paths of length 1 to K in the graph and sum them up. Lets simplify the graph. Observe that both edges from X to Y and Y to X exist if and only if gcd(X, K) = gcd(Y, K). So, lets group the numbers from 0 to K - 1 such that in each group all the numbers have same gcd with K. Observe that the graph formed by these groups as components is a DAG. So now we can do DP to find the number of paths starting from a particular component.

Number of distinct values of gcd(i, K) are equal to the number of divisors of K. Since, K is upto 10¹², the number of divisors can be upto M = 7000. So, the final graph consists of at max M nodes and C(M, 2) edges.

The path starting from a component would look like :

some non-empty sequence of elements from this component + sequence from the child components

The first part is equal to : , where n is the number of elements in that component and i is the length of the chosen sequence from this part.

The second part would be the sum of dp values of all components reachable from current component and an extra +1 for ending at the current component only. The Final answer would be the sum of dp values of all components, as the path can start from any component.

For the first part observe that f[n]%mod = f[n%mod]. (Proof is easy).

Since, mod is upto 10⁶, we can calculate the f values before hand, using the recurrence f[n] = n * (f[n - 1] + 1).

So, overall complexity would be O(mod + M²) where M is the number of divisors of K.

#include <bits/stdc++.h>

#define int         long long
#define pb          push_back
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define x           first
#define y           second
#define sz(x)       (int)x.size()
#define endl        '\n'
#define hell        1000000007
#define rep(i,a,b)  for(int i=a;i<b;i++)
using namespace std;
vi divisors;
int k,mod,a[10005],b[1000006],dp[10005],ans;
void solve(){
    divisors.clear();
    ans=0;
    memset(dp,0,sizeof dp);
    memset(a,0,sizeof a);
    cin>>k>>mod;
    b[0]=1;
    rep(i,1,mod) b[i]=(i*b[i-1]+1)%mod;
    for(int i=1;i*i<=k;i++){
        if(k%i==0){
            divisors.pb(i);
            if(i*i!=k) divisors.pb(k/i);
        }
    }
    sort(all(divisors));
    for(int i=sz(divisors)-1;i>=0;i--){
        a[i]=k/divisors[i];
        dp[i]=1;
        rep(j,i+1,sz(divisors)){
            if(divisors[j]%divisors[i]==0){
                a[i]-=a[j];
                dp[i]=(dp[i]+dp[j])%mod;
            }
        }
        dp[i]=dp[i]*(b[a[i]%mod]-1+mod)%mod;
        ans=(ans+dp[i])%mod;
    }
    cout<<ans<<endl;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}